בעיית הגלריה לאמנות

מתוך ויקיפדיה, האנציקלופדיה החופשית

יש לך הודעות חדשות (השווה לגרסה הקודמת).

בתחום הגאומטריה החישובית, בעיית הגלריה לאמנות שהוצגה בשנת 1973 עוסקת בגלריה לאומנות התחומה על-ידי מספר סופי של קירות ישרים, ושואלת מהו מספר השומרים הקטן ביותר כך שכל נקודה בגלריה נצפית על-ידי שומר אחד לפחות. הניסוח המתמטי עוסק במספר המינימלי של נקודות במצולע חסר חורים, כך שכל נקודה בפוליגון ניתן לחבר לאחד השומרים, באופן שהקו המחבר נמצא כולו בתוך המצולע.

הפתרון הכללי לבעיה זו (שאינו תלוי בצורת הפוליגון, אלא רק במספר קודקודיו), מסתמך על היכולת למצוא שילוש פוליגון עבור כל פוליגון פשוט. השיטה היא זו: ראשית מוצאים שילוש לפוליגון המבוקש. אחר כך צובעים בשלושה צבעים את הקודקודים של הפוליגון, כך ששני קודקודים המחוברים בקו לא יהיו בעלי אותו צבע. ניתן להוכיח כי צביעה שכזו תמיד אפשרית וגם לספק אלגוריתם למציאתה.

כעת בוחרים את הצבע שבו נצבע מספר הנקודות הקטן ביותר. בוחרים בתור ה"שומרים" את הנקודות שצבועות באותו צבע.

מכיוון שקודקודי כל אחד מהמשולשים בשילוש של הפוליגון צבועים בכל שלושת הצבעים (כי כל שני קודקודים מחוברים בקו, ולכן אם היו שני קודקודים בעלי אותו צבע, זה היה סותר את דרך הצביעה) הרי שבכל אחד מהמשולשים נמצא שומר. מכיוון שמשולש הוא צורה קמורה, די בשומר זה כדי לשמור על כל המשולש. לכן קבוצת השומרים שנבחרה מספיקה כדי לשמור על הפוליגון כולו.

אם לפוליגון $\ n$ קודקודים, הרי שמספר הנקודות שנצבעו בצבע שהופיע הכי מעט פעמים לא עולה על $\ \lfloor {\frac{n}{3}}\rfloor$ . ניתן להוכיח כי זהו חסם תחתון למספר השומרים - קיימים פוליגונים שבהם נדרש כמספר הזה של שומרים.

הבעיה של מציאת המספר המינימלי של שומרים עבור פוליגון מסוים (שיכול להיות קטן בהרבה מ- $\ \lfloor {\frac{n}{3}}\rfloor$ - למשל, לפוליגון קמור די בשומר יחיד) היא בעיה NP-קשה.

מקור: http://he.wikipedia.org../../../%D7%91/%D7%A2/%D7%99/%D7%91%D7%A2%D7%99%D7%99%D7%AA_%D7%94%D7%92%D7%9C%D7%A8%D7%99%D7%94_%D7%9C%D7%90%D7%9E%D7%A0%D7%95%D7%AA.html

קטגוריה: גאומטריה חישובית

בעיית הגלריה לאמנות

מתוך ויקיפדיה, האנציקלופדיה החופשית

Views

ניווט

קהילה

חיפוש

שפות אחרות