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

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

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

איור 1: החלק שנקלט במצלמה אחת (מסומנת באיקס) במוזאון

לכמה מצלמות נזדקק כדי לאבטח את חלל המוזאון בלי שנתרושש מרכישת מצלמות מיותרות? נראה שמספר המצלמות המינימלי שיספיק עבור מצולע ספציפי תלוי ברמת ה"סיבוך" – ככל שהמצולע מסובך יותר, סביר שיידרשו יותר מצלמות. נסו לצייר מצולע כלשהו ולומר כמה מצלמות יספיקו כדי לאבטח אותו!

נשאל שאלה כללית שונה מעט: מהו המספר המינימלי של מצלמות שיספיק לאבטחת כל מוזאון מצולע בעל N צלעות, תהא צורתו אשר תהא? [2,1]
במילים אחרות, עלינו לומר מהי הכמות החסכונית ביותר של מצלמות שתספיק בוודאות לכל מצולע בעל N צלעות, מסובך ככל שיהיה, על פי מספר הצלעות בלבד. למשל, כאשר N=3 מדובר במשולשים, ואז תמיד תספיק מצלמה אחת. מה לגבי מרובעים? מחומשים? תכף יתברר לנו שהנוסחה פשוטה מאוד!

בשנת 1973 הציג ויקטור קְלי [3] את הבעיה לווָאצְלָב חְווָאטָל [4], אשר פתר אותה בתוך חצי שנה, אבל בדרך מסובכת למדי. למזלנו, ב-1978 מצא סטיב פִיסְק דרך מפתיעה, אלגנטית ופשוטה יחסית, ואותה נציג בפסקאות הבאות. לעומתנו, פיסק דווקא הסתפק במאמר מהקצרים בהיסטוריה, מאמר המציג את ההוכחה בפסקה אחת בלבד [5].

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

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

איור 2: מצולעים קמורים (מימין) ומצולעים לא-קמורים (משמאל)

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

למזלנו, אכן אפשר לחלק למשולשים כל מצולע, ואפילו בתנאים מחמירים מסוימים: נתמקד בחלוקות שנוצרות מהעברת אלכסונים בין קודקודים קיימים, כלומר קטעים המחברים בין קודקודי המצולע, ומבלי ליצור קודקודים חדשים. במצב כזה כל מצולע בעל N צלעות ניתן לחלק ל-N-2 משולשים (למשל, מרובע תמיד אפשר לחלק ל- 2=4-2 משולשים על ידי העברת אלכסון אחד, ומחומש אפשר לחלק ל-3 משולשים – נסו והיווכחו). אפשר לחלק גם בדרך שמוסיפה קודקודים, אבל אז אולי נקבל יותר משולשים. חלוקות מהסוג שבו לא נוספים קודקודים נקראות "שילוש" (טריאנגולציה). ישנם אלגוריתמים יעילים לביצוע שילושים, כך שאפשר לתת למחשב לבצע את העבודה  [1].

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

אחרי שחילקנו ל- N-2 משולשים, מצלמה בכל משולש בוודאי תספיק, וסיימנו... או שאפשר לחסוך עוד? לשני משולשים שחולקים צלע תספיק מצלמה אחת, שתוצב על הצלע המשותפת. ואם יש כמה משולשים שלהם קודקוד משותף, הצבת מצלמה בקודקוד זה תספיק לכל אותם משולשים. אז עד כמה אפשר לחסוך באמת?

נזדקק לשיטה להצבת מצלמות במשולשים שנוצרים בחלוקה. לעזרתנו בא רעיון מתחום תורת הגרפים – צביעה של קודקודי המשולשים בחלוקה (ראו פוסטים נוספים בנושאי תורת הגרפים וצביעה [6, 7]). נצטייד בשלושה צבעים – אדום, כחול וירוק – ונצבע כל קודקוד באחד הצבעים כך שבכל משולש לא יהיו שני קודקודים בצבע זהה (משמע בכל משולש יהיו קודקוד אחד אדום, קודקוד כחול וקודקוד ירוק). רק רגע... זה אפשרי בכלל? ציירו מצולע על דף, חלקו אותו למשולשים ונסו לצבוע את הקודקודים לפי הכללים. זה די כיף, ובאופן כללי – אכן אפשרי. לא נציג כאן הוכחה מפאת קוצר המקום.

איור 4: מצולע מחולק למשולשים וכל קודקוד צבוע באחד משלושת הצבעים כך שאין שני קודקודים בעלי צבע זהה על אותה צלע

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

אז כמה מצלמות יספיקו לנו? כמה קודקודים יש בכל צבע? לא ייתכן שיש יותר מ-3/N קודקודים בכל אחד מהצבעים, כי אילו היו, מספר הקודקודים הכולל היה גדול מ-N. לכן יש צבע שמופיע 3/N פעמים לכל היותר. אם נבחר בצבע זה, בטוח שיספיקו לנו 3/N מצלמות (או פחות). אם N=4 אז ⅓N/3=1, כלומר יספיקו לנו ⅓1 מצלמות. שליש מצלמה? איזו מנהלת מוזיאון תקשיב לנו אם נגיד לה להתקין מצלמה אחת ושליש?

טוב, במקרה ש-N אינו מתחלק ב-3, כדי להגיע לתשובה סבירה, כלומר מספר שלם, עלינו לעגל כלפי מעלה או מטה. אם נעגל למעלה נקבל מספר שיספיק לבטח, ואולי נמליץ על מצלמה אחת מיותרת. נסמן ב-[N/3] את העיגול למטה של N/3. במעט עבודה ניתן להגיע למסקנה שתמיד יש צבע שמופיע בצביעה שלנו לא יותר מ-[N/3] פעמים. למשל עבור 4=N נעגל את ⅓1 ל-1 ונקבל שתמיד מספיק להציב מצלמה אחת בלבד! (כן, גם אם המרובע אינו קמור.) אם כן, הגענו למסקנה ש-[N/3] מצלמות מספיקות לכל מצולע בעל N צלעות.

האם אפשר לחסוך עוד? בחלק מהמצולעים בוודאי אפשר לחסוך (למשל בקמורים תמיד תספיק מצלמה אחת). אבל מתברר שבגלריה בצורת מסרק בעל N צלעות ו-[N/3] חדרים שפיציים (ראו איור 5) אי אפשר להסתדר עם מספר קטן יותר של מצלמות, לכן המספר [N/3] הוא התשובה הסופית.

איור 5: גלריית המסרק – מספר המצלמות הדרושות הוא כמספר השפיצים, אי אפשר לחסוך

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

ליווי מדעי: נעה זילברמן
עריכה: סמדר רבן

מקורות והרחבות

[1] להרחבה ופרטים ראו פרק 3 בספר: Computational Geometry (Algorithms and Applications); Berg, Cheong, van Kreveld, Overmars.

[2] מערך שיעור ומצגת בנושא בעיית השמירה במוזאון, "הבזק", הטכניון

[3] ויקטור קלי

[4] ואצלב חוואטל

[5] המאמר המקורי של פיסק

[6] מהי תורת הגרפים? פוסט מבוא במדע גדול, בקטנה

[7] פוסט על הלמה של שפרנר, המסביר גם הוא על צביעת גרפים