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

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

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

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

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

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

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

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

השימוש בעץ חוסך לנו זמן. במקום לעבור על כל תאי הטלפון - חיפוש אשר כרוך בזמן חישוב רב בסיבוכיות חישוב ליניארית, כלומר ביצוע חישוב מרחק עבור כל אחד מתאי הטלפון - נחפש רק את חלקם בסיבוכיות חישוב לוגריתמית, שהיא חסכונית יותר ומאפשרת לחפש את תאי הטלפון באופן מושכל [3]. לדוגמה, אם ישנם 1000 תאי טלפון בעיר נבצע רק 10 פעולות השוואה. כך, בעזרת בניית דיאגרמת הוורונוי המייצגת את תאי הטלפון ברחבי העיר, גיבורינו יוכלו לחשב בתוך זמן קצר את המרחק אל תא הטלפון הקרוב אליהם ביותר.

דיאגרמת וורונוי היא שיטה פשוטה המאפשרת למידה בעזרת משחקים. למשל, כיצד תיראה מפת ארצות הברית אם שטחי המדינות היו מורכבים מהמרחק הקצר ביותר לערי הבירה שלהן [4]. באופן פרקטי, דיאגרמת וורונוי היא כלי שימושי אשר יכול לסייע בתחומים שונים, כגון ניווט בין נקודות עניין ומציאת מסלול נסיעה אופטימלי, מציאת שדה התעופה הקרוב ביותר ותכנון מסלול רובוטי תוך הימנעות ממכשולים, ועוד שימושים רבים נוספים. ההיסטוריה מספרת ששיטה דומה אף עזרה לד"ר ג'ון סנואו (אחד שדווקא ידע די הרבה) להבין את מקור ההדבקה של מחלת הכולרה ברחוב בעייתי בלונדון בשנת 1854 [5]. 

הערות, קישורים וקריאה נוספת:

[1] דף הסרט של המטריקס באתר IMDB

[2] הסבר נוסף על עצי חיפוש

[3] הסבר נוסף על סיבוכיות הזמן של בניית דיאגרמת וורנוי

[4] united states of voronoi

[5] הסבר נוסף על ד"ר ג'ון סנואו וגילוי מקור הכולרה