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

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

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

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

חסם עליון[עריכת קוד מקור | עריכה]

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

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

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

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

סיבוכיות[עריכת קוד מקור | עריכה]

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