בעיית הגלריה לאמנות
מתוך ויקיפדיה, האנציקלופדיה החופשית
בעיית הגלריה לאמנות היא בעיה תאורטית מפורסמת בתחום הגאומטריה החישובית, העוסקת במבנה של מצולעים מישוריים. הבעיה, שהוצגה בשנת 1973, מבקשת למצוא את מספר השומרים הקטן ביותר שיוכלו, מבלי לעזוב את משמרתם, להשגיח על כל פינה בגלריה לאמנות, שקירותיה ישרים.
באופן פורמלי, נקודה A "משגיחה" על נקודה B בתוך מצולע, אם הקו הישר המחבר אותן נמצא כולו בתוך המצולע. בהינתן מצולע חסר חורים, השאלה היא מהו המספר הקטן ביותר של נקודות שכל נקודה במצולע נתונה תחת השגחתה של אחת מהן.
[עריכה] חסם עליון
הפתרון הכללי לבעיה זו (שאינו תלוי בצורת הפוליגון, אלא רק במספר קודקודיו), מסתמך על היכולת למצוא שילוש פוליגון עבור כל פוליגון פשוט. השיטה היא זו: ראשית מוצאים שילוש לפוליגון המבוקש. אחר כך צובעים בשלושה צבעים את הקודקודים של הפוליגון, כך ששני קודקודים המחוברים בקו לא יהיו בעלי אותו צבע. ניתן להוכיח כי צביעה שכזו תמיד אפשרית וגם לספק אלגוריתם למציאתה.
כעת בוחרים את הצבע שבו נצבע מספר הנקודות הקטן ביותר. בוחרים בתור ה"שומרים" את הנקודות שצבועות באותו צבע.
מכיוון שקודקודי כל אחד מהמשולשים בשילוש של הפוליגון צבועים בכל שלושת הצבעים (כי כל שני קודקודים מחוברים בקו, ולכן אם היו שני קודקודים בעלי אותו צבע, זה היה סותר את דרך הצביעה) הרי שבכל אחד מהמשולשים נמצא שומר. מכיוון שמשולש הוא צורה קמורה, די בשומר זה כדי לשמור על כל המשולש. לכן קבוצת השומרים שנבחרה מספיקה כדי לשמור על הפוליגון כולו.
אם לפוליגון 
קודקודים, הרי שמספר הנקודות שנצבעו בצבע שהופיע הכי מעט פעמים לא עולה על 
. ניתן להוכיח כי זהו חסם עליון למספר השומרים - קיימים פוליגונים שבהם נדרש כמספר הזה של שומרים.
[עריכה] סיבוכיות
הבעיה של מציאת המספר המינימלי של שומרים עבור פוליגון מסוים (שיכול להיות קטן בהרבה מ- - למשל, לפוליגון קמור די בשומר יחיד) היא בעיה NP-קשה.
