יחידה 6 מיקום נקודה ומפה טרפזית
6.1 הקדמה
מפה המתארת חלוקה למדינות, כמו מפת ארצות הברית המופיעה משמאל, היא בעצם גרף מישורי המתואר באמצעות צלעות, פאות וקודקודים. כל מדינה או אזור במפה מתאימים לפאה של הגרף. ביחידה הזו נעסוק בבעיה הבסיסית הבאה: בהינתן הקואורדינטות של נקודה כלשהי על המפה, לאיזו מדינה שייכת הנקודה?6.2 מפה טרפזית
6.2.1 פתרון נאיבי: חלוקה לרצועות
תהי \(\mathcal{S}\) מפה מישורית, כפי שהגדרנו ביחידה 2: \(\mathcal{S}\) היא שיכון של גרף מישורי במישור, כך שכל הצלעות שלו הן קטעים ישרים. נרצה לבנות מבנה נתונים שיענה על שאילתות מהסוג הבא: בהינתן נקודה \(q\) במישור, מצא את הפאה שבה \(q\) נמצאת.
שימו לב שכדי למצוא את הפאה שבה \(q\) נמצאת, מספיק לבדוק למשל איזו צלע של \(\mathcal{S}\) הנקודה \(q\) “רואה” מעליה. לכן בחלק הראשון של סעיף 6.1 בספר הלימוד מתואר פתרון נאיבי ופשוט לבעיה, על ידי חלוקה של המפה לרצועות (slabs): נעביר ישר אנכי דרך כל אחד מהקודקודים של \(\mathcal{S}\). האזור שנמצא בין שני ישרים עוקבים כאלו הוא רצועה אנכית. בהינתן שמספר הקודקודים במפה \(\mathcal{S}\) הוא n, ניתן למצוא את הרצועה שבה נמצאת נקודה נתונה \(q\) בזמן \(O (\log n )\) על ידי חיפוש בינארי. כל רצועה “נחתכת” על ידי לכל היותר \(n\) צלעות של \(\mathcal{S}\). הצלעות כמובן אינן חותכות זו את זו, ואין קודקודים של \(\mathcal{S}\) בתוך הרצועה. לכן נוכל לשמור את רשימת הצלעות האלו בסדר ממוין, ואז למצוא את הצלע שהנקודה \(q\) “רואה” מעליה על ידי חיפוש בינארי, כלומר שוב \(O (\log n )\).
בדרך זו, זמן השאילתה שנקבל הוא \(O (\log n )\). אך מהו גודל המבנה וזמן העיבוד המקדים? באיור למטה ניתן לראות דוגמה למקרה שבו גודל המבנה הוא \(\Theta ( n^2 )\) (מדוע?).
6.2.2 פירוק לטרפזים
שימו לב שהחלוקה לרצועות שראינו בעמוד הקודם יוצרת מפה מישורית \(\mathcal{S'}\) שבה כל פאה היא טרפז או משולש (או פאה אינסופית דמוית טרפז/משולש). המפה \(\mathcal{S'}\) היא עידון (refinement) של המפה המקורית \(\mathcal{S}\), כלומר כל פאה של \(\mathcal{S'}\) מוכלת לחלוטין בפאה של \(\mathcal{S}\), ולכן אם מצאנו שנקודת השאילתה נמצאת בפאה מסוימת של \(\mathcal{S'}\), נוכל לדעת לאיזו פאה של \(\mathcal{S}\) היא שייכת. העידון בעזרת חלוקה לרצועות מוביל למבנה נתונים בגודל ריבועי (במקרה הגרוע), ולכן אינו מעשי. בחלק זה נראה עידון אחר שסיבוכיות הזיכרון שלו לא תהיה גדולה בהרבה מזו של \(\mathcal{S}\), ושעדיין יאפשר לנו לענות על שאילתות מיקום נקודה בקלות יחסית.
להרחבה ולהעשרה: הנחת מצב כללי
בשיטת הפירוק לטרפזים אנחנו מניחים שבאוסף הקטעים הנתון אין שתי נקודות קצה בעלות אותה קואורדינטת \(x\). הנחה זו אינה ריאלית, אך כפי שכבר ראינו בעבר, קיימות מספר שיטות המאפשרות לנו לטפל במצב לא כללי – למשל סיבוב המישור או קביעת סדר לקסיקוגרפי. הדיון בפתרונות אלו עבור המבנה של מפת טרפזים מופיע בסעיף 6.3 בספר הלימוד.
במצב לא כללי, יתכן למשל שיהיו 6.3 שאילתות מיקום נקודה
6.3.1 מבנה נתונים לשאילתות מיקום נקודה
יהי \(\mathcal{S}\) אוסף של \(n\) קטעים במצב כללי שאינם נחתכים.
ניתן לבנות את המפה הטרפזית \(\mathcal{T}(\mathcal{S})\) בקלות יחסית על ידי שימוש בשיטת הישר הסורק (חשבו כיצד). הבעיה היא שבשיטה זו לא נוכל לבנות מבנה נתונים התומך בשאילתות מיקום נקודה, שהוא המטרה המרכזית שלנו ביחידה זו. איך ייראה מבנה נתונים כזה?
בחלק זה נתאר את מבנה החיפוש \(\mathcal{D}\) שיאפשר לנו לבצע שאילתות מיקום נקודה במפה הטרפזית \(\mathcal{D}\). בהמשך היחידה נראה אלגוריתם אינקרמטלי-רנדומי שבונה את המפה הטרפזית \(\mathcal{T}(\mathcal{S})\) ואת מבנה הנתונים \(\mathcal{D}\) גם יחד.
תיאור מבנה הנתונים
מבנה הנתונים \(\mathcal{D}\) יהיה גרף מכוון חסר מעגלים (DAG), שבו שלושה סוגי צמתים:
- צומת (פנימי) x – מתאים לנקודת קצה של קטע מ-\(\mathcal{S}\) (מסומן בעיגול לבן).
- צומת (פנימי) y – מתאים לקטע מ-\(\mathcal{S}\) (מסומן בעיגול אפור).
- עלה – מתאים לטרפז במפה \(\mathcal{T}(\mathcal{S})\) (מסומן בריבוע).
נוסף על כך, לגרף יש שורש יחיד ובדיוק עלה אחד לכל טרפז במפה \(\mathcal{T}(\mathcal{S})\). למשל באיור למטה, לעלה של טרפז C יש מצביעים משני קודקודים פנימיים.
הרעיון בבנייה זו דומה לעצי kd שראינו ביחידה 5: לכל צומת פנימי, ההסתעפות ימינה או שמאלה תלויה בתשובה לשאלה המתאימה לסוג הצומת.
אלגוריתם השאילתה
בהינתן נקודת שאילתה q, נתחיל את החיפוש מהשורש עד שנגיע לעלה:
- אם הגענו לצומת \(x\) המתאים לנקודת קצה \(p\), נשאל: “האם \(q\) מימין או משמאל לישר האנכי שעובר דרך p?”. אם התשובה היא “מימין” – נמשיך ימינה, אחרת שמאלה.
- אם הגענו לצומת \(y\) המתאים לקטע \(s\), נשאל: “האם \(q\) מעל או מתחת לקטע \(s\)?”. אם התשובה היא “מתחת” – נמשיך ימינה, אחרת שמאלה. שימו לב שכדי שהשאלה הזו תהיה הגיונית, נצטרך להבטיח שבשלב זה הישר האנכי שעובר דרך \(q\) חותך את \(s\).
כשנגיע לעלה, נבדוק אם הטרפז המתאים לו מכיל את \(q\).
ענו על השאלה הבאה:
נתון מבנה החיפוש למטה.
ידוע שנקודת שאילתה נמצאת:
- מימין לישר האנכי העובר בנקודה \(p_1\).
- משמאל לישר האנכי העובר בנקודה \(q_1\).
- מתחת לקטע \(s_1\).
באילו מהטרפזים ייתכן שהנקודה נמצאת?
אם בנוסף ידוע שהנקודה נמצאת:
- משמאל לישר האנכי העובר בנקודה \(q_2\).
- מעל לקטע \(s_2\).
באילו מהטרפזים ייתכן שהנקודה נמצאת?
(פתרון)
TODO
6.3.2 אלגוריתם אינקרמנטלי-רנדומי
בחלק זה נתאר אלגוריתם אינקרמנטלי לבניית מבנה החיפוש \(\mathcal{D}\) והמפה הטרפזית \(\mathcal{T}(\mathcal{S})\) גם יחד. האלגוריתם מוסיף את הקטעים מהאוסף \(\mathcal{S}\), זה אחר זה בסדר רנדומי, ובכל פעם מעדכן את מבנה החיפוש והמפה בהתאם לקטע החדש שנוסף.
הסיבה לכך שנבחר סדר רנדומי על הקטעים היא שבאופן זה נוכל לצפות לזמני ריצה ולסיבוכיות מקום יעילים, בדומה לאלגוריתם האינקרמנטלי-רנדומי לתכנון לינארי במישור שראינו ביחידה 4. נדון בכך בעמוד הבא של חלק זה.
6.3.3 ניתוח האלגוריתם
הסדר שבו האלגוריתם TrapezoidalMap מוסיף את הקטעים משפיע מאוד על גודל מבנה החיפוש \(\mathcal{D}\) ועל זמן השאילתה. למעשה, ייתכן סדר שבו האלגוריתם ירוץ בזמן ריבועי, סיבוכיות הזיכרון של \(\mathcal{D}\) תהיה ריבועית, וזמן השאילתה יהיה לינארי. לכן, בדומה לאלגוריתם האינקרמנטלי-רנדומי לתכנון לינארי במישור שראינו ביחידה 4, גם כאן האלגוריתם מגריל את סדר הוספת הקטעים מראש, ונוכל להראות שבתוחלת יתקבל מבנה חיפוש עם סיבוכיות זיכרון לינארית, ותוחלת זמן השאילתה תהיה \(O (\log n )\).
תרגיל: מהו המקרה הגרוע ביותר?
נסו לתאר דוגמה לאוסף של \(n\) קטעים ושל הסדר שלהם, כך שהאלגוריתם האינקרמנטלי (הלא רנדומי) ירוץ בזמן \(O ( n^2 )\).
רעיון ההוכחה עבור זמן השאילתה
תהי \(q\) נקודת שאילתה. נרצה להעריך את תוחלת אורך המסלול שבו נלך כאשר נחפש במבנה \(\mathcal{D}\) את הטרפז שמכיל את \(q\) (מספר הצמתים מהשורש לטרפז). לשם כך, ננסה להבין כיצד המסלול משתנה במהלך ריצת אלגוריתם הבנייה של \(\mathcal{D}\).
למשל, ניתן להראות שבכל פעם שקטע חדש נוסף למבנה, המסלול יתארך לכל היותר בשלושה צמתים. לפיכך ניתן לומר שאורך המסלול הוא לכל היותר \(3n\). זהו חסם עבור המקרה הגרוע, אך אנו מעוניינים במקרה הממוצע (על פני כל \(n!\) הסדרים האפשריים), ולכן ננסה לחשב את ממוצע מספר הצמתים שנוספו למסלול בכל איטרציה של האלגוריתם.
נסמן ב-\(X_i\) (עבור \(1 \le i \le n\)) את מספר הצמתים על המסלול שנוספו באיטרציה ה-\(i\)-ית (כלומר לאחר הוספת הקטע \(s_i\)). לפיכך, \(X_i\) הוא משתנה מקרי התלוי בסדר הוספת הקטעים, ולכן תוחלת אורך המסלול אל הטרפז המכיל את \(q\) היא \(E[ \sum_{i=1}^{n} X_i ]\), ומלינאריות התוחלת \(\sum_{i=1}^{n} E[X_i]\).
מכיוון שבכל איטרציה נוספים לכל היותר שלושה צמתים למסלול, מתקיים \(X_i \le 3\). לכן, אם נסמן ב-\(P_i\) את ההסתברות לכך שקיים צומת במסלול שנוצר באיטרציה ה-\(i\)-ית, נקבל \(E[ X_i ] \le 3 P_i\).
האבחנה המרכזית בהוכחה היא שבאיטרציה ה-\(i\)-ית נוסף קודקוד למסלול שלנו רק אם הטרפז שמכיל את \(q\) בדיוק לפני הוספת \(s_i\) שונה מהטרפז המכיל את \(q\) מייד לאחר הוספת \(s_i\). לכן, בדומה להוכחה שראינו ביחידה 4, נוכל לנתח את ההסתברות לכך שהטרפז המכיל את \(q\) משתנה בין האיטרציה ה-\(i – 1\) לאיטרציה ה-\(i\)-ית בשיטת הניתוח לאחור (backwards analysis). כלומר, נסתכל על המפה שהתקבלה מייד לאחר הוספת \(s_i\), ונשאל מה ההסתברות לכך שהטרפז \(\Delta\) המכיל את \(q\) במפה זו ייעלם אם נוציא את \(s_i\). שימו לב שהטרפז \(\Delta\) ייעלם אם ורק אם אחד מהשדות המגדירים אותו (\(top(\Delta)\), \(bottom(\Delta)\), \(leftp(\Delta)\), \(rightp(\Delta)\)) ייעלם. ההסתברות לכך ש-\(s_i\) הוא הקטע שמגדיר את \(top(\Delta)\) למשל, היא \(\frac{1}{i}\), ובאופן דומה ניתן לחשב זאת עבור \(bottom(\Delta)\), \(leftp(\Delta)\), \(rightp(\Delta)\). לכן נקבל \(P_i \le \frac{4}{i}\), ונוכל לחשב שתוחלת אורך המסלול היא \(O (\log n )\).