יחידה 5 חיפוש בתחומים אורתוגונליים
5.1 הקדמה
5.1.2 חיפוש במסדי נתונים
מסדי נתונים המאחסנים רשומות בטבלה הם כלי מרכזי לארגון מידע ביישומים רבים. כפי שראינו בהקדמה לקורס, אף שבמבט ראשון נדמה שאין קשר בין מסדי נתונים כאלו לגיאומטריה, הקשר הזה אכן קיים עבור סוגים מסוימים של שאילתות.הייצוג הגיאומטרי של מסד הנתונים נעשה באמצעות אוסף של נקודות במרחב ה-\(d\) ממדי: כל רשומה מיוצגת באמצעות נקודה במרחב, כאשר כל שדה של הרשומה מתאים לקואורדינטה. עבור שאילתה המבקשת את אוסף הרשומות הנמצאות בתחום מסוים של ערכים (בשדה אחד או יותר), הייצוג הגיאומטרי הוא תחום אורתוגונלי \(R\), כלומר, תיבה \(d\)-ממדית מקבילה לצירים. במישור זהו מלבן שצלעותיו מקבילות לצירים, ובמרחב התלת-ממדי זוהי תיבה שפאותיה מקבילות לצירים.
בפרק זה נציג שני מבני נתונים לאחסון אוסף \(P\) של נקודות במרחב ה-\(d\) ממדי, כך שנוכל לענות ביעילות על שאילתות מהסוג הבא: בהינתן תחום אורתוגונלי \(R\), אילו מהנקודות של \(P\) נמצאות בתוך \(R\).
5.1.3 חיפוש בתחומים על הישר
בעיות רבות בגיאומטריה חישובית נעשות פשוטות הרבה יותר כאשר הן נתונות בממד אחד, ובמחקר התיאורטי מופיעים לעיתים קרובות פתרונות בממד אחד לבעיות מורכבות, כצעד מקדים לפתרונות בממדים גבוהים יותר. לכן, לפני שניגש לפתרון הבעיה של חיפוש בתחומים בשני ממדים או יותר, ננסה קודם להבין כיצד ניתן לפתור את הבעיה עבור אוסף \(P\) של נקודות מממד אחד, כלומר אוסף של נקודות שכולן על ישר אחד. שימו לב שהשאילתה על הישר היא פשוט טווח של ערכים, \(R=[x,x']\).
אפשרות אחת לפתרון היא למיין את נקודות \(P\) ולשמור אותן במערך. בהינתן טווח \([x,x']\), נמצא בעזרת חיפוש בינארי את הנקודה הראשונה במערך שגדולה מ-\(x\) או שווה לו, ואז נעבור על תאי המערך לפי הסדר החל מנקודה זו, ונדווח על נקודות כל עוד הן קטנות מ-\(x'\) או שוות לו. זמן השאילתה הוא \(O(\log n + k)\) כאשר \(k\) הוא מספר הנקודות בפלט. זמן העיבוד המקדים הוא \(O( n \log n)\) וסיבוכיות המקום היא \(O(n)\). לפתרון המשתמש במערך יש שני חסרונות: הוא לא דינמי (כלומר לא ניתן להוסיף או למחוק נקודות), ולא ניתן להכליל אותו לממדים גבוהים. לכן סעיף 5.1 בספר הלימוד מתאר פתרון המשתמש בעץ חיפוש בינארי, שבו הנקודות מופיעות בעלים. כל קודקוד פנימי מכיל את הערך המקסימלי של עלה המופיע בתת-עץ השמאלי שלו. בהינתן עץ חיפוש \(T\) וטווח \([x,x']\), אלגוריתם השאילתה 1DRangeQuery מוצא את הקודקוד שבו המסלולים מהשורש ל-\(x\) ול-\(x'\) מתפצלים, ואז מחזיר את כל הנקודות בעלים שנמצאים מימין להמשך המסלול ל-\(x\), ואת הנקודות בעלים שנמצאים משמאל להמשך המסלול ל-\(x'\). אלו בדיוק הערכים בעץ הנמצאים בין \(x'\) ל-\(x\).
בהמשך יחידה זו נראה שתי דרכים להכללת פתרון זה עבור ממדים גבוהים.
5.2 חיפוש בתחומים במישור
5.2.1 עצי kd
מבנה הנתונים הראשון שנראה עבור חיפוש בתחומים בשני ממדים נקרא עץ kd. עץ זה הוא הכללה של עץ החיפוש שראינו עבור נקודות בממד אחד, שבו בכל רמה של העץ משנים את הקואורדינטה שלפיה בוחרים את החציון.צפו בסרטון הבא:
ניתן לבנות עץ kd עבור אוסף של \(n\) נקודות בזמן \(O(n\log n)\). סיבוכיות המקום שלו היא \(O(n)\), וזמן השאילתה הוא \(O(\sqrt{n}+ k)\), כאשר \(k\) הוא גודל הפלט, כלומר מספר הנקודות הנמצאות בתחום הנתון. בסעיף 5.2 מתואר האלגוריתם BuildKdTree שבונה את העץ, ואלגוריתם השאילתה SearchKdTree. קראו בעיון את ניתוח זמן הבנייה, סיבוכיות המקום וזמן השאילתה של עץ הkd.
ענו על השאלה הבאה:
התבוננו בחלוקה שנוצרה עבור עץ הkd והתחום המלבני שבאיור, וענו על השאלות הבאות:
- אילו מהנקודות ייבדקו (אך לא בהכרח ידֻווחו) בשורה 2 של האלגוריתם SearchKdTree?
- אילו מהנקודות ידווחו על ידי הפרוצדורה ReportSubtree?
(פתרון)
(TODO)
תרגיל: תחומים שאינם מלבניים
שימו לב שניתן להכליל את אלגוריתם השאילתה גם עבור תחומים שאינם מלבניים. כדי שהאלגוריתם יהיה יעיל עבור תחום \(R\) שאינו מלבני, התחום חייב להיות מתואר בצורה שתאפשר את שתי הפעולות הבאות בזמן קבוע:
- לבדוק אם \(R\) מכיל נקודה נתונה.
- לבדוק אם \(R\) נחתך עם תחום מלבני המתאים לצומת כלשהו או מכיל תחום כזה.
אם \(R\) הוא מצולע קמור בעל \(c\) צלעות, כיצד נוכל לבצע את הבדיקות האלו? ומה יהיה זמן הריצה שלהן? מה אם \(R\) הוא עיגול הנתון על ידי המרכז והרדיוס שלו?
5.2.2 עצי תחומים (Range Trees)
בחלק זה נראה מבנה נתונים אחר לחיפוש בתחומים במישור, ושמו עץ תחומים, (range tree). גם הוא הכללה של עץ החיפוש שראינו עבור נקודות על הישר, אך באופן שונה: כאן כל קודקוד פנימי בעץ הממיין את הנקודות לפי קואורדינטת ה-\(x\), יכיל מצביע לעץ נוסף הממיין את העלים בתת-עץ שלו לפי קואורדינטת ה-\(y\).
צפו בסרטון הבא:
מבחינת זמן השאילתה, במקרה הגרוע עץ תחומים יעיל הרבה יותר מעץ kd – זמן השאילתה שלו הוא \(O( \log^2 n + k)\) בלבד, לעומת \(O( \sqrt{n}+k)\) בעצי kd. שיפור זה מאלץ אותנו לשלם מעט בסיבוכיות המקום – \(O( n \log n)\) לעומת \(O( n)\). בסעיף 5.3 בספר הלימוד מתואר האלגוריתם Build2DRangeTree שבונה את העץ, ואלגוריתם השאילתה 2DRangeQuery. קראו בעיון את ניתוח זמן הבנייה, סיבוכיות המקום וזמן השאילתה של עץ תחומים.
5.3 הרחבות
5.3.1 ממדים גבוהים
בשתי הפסקאות האחרונות של סעיף 5.2 בספר הלימוד מתוארת בקצרה בנייה של עציkd בממד \(d>2\). עבור \(d\) קבוע, זמן הבנייה נשאר \(O( n \log n)\) וסיבוכיות הזיכרון נשארת \(O( n)\). לעומת זאת, זמן השאילתה הוא \(O( n^{1-\frac{1}{d}}+k)\), והוא מתקרב ל-\(O( n)\) ככל ש-\(d\) גדל. בסעיף 5.4 מתוארת הרחבה של עצי תחומים לממד \(d>2\). כאן זמן העיבוד המקדים וסיבוכיות המקום הם \(O( n \log^{d-1} n)\), וזמן השאילתה הוא \(O( \log^d n +k)\).
5.3.2 אוסף נקודות כללי
בסעיפים 5.1–5.3 בספר הלימוד אנו מניחים שאין באוסף הנתון שתי נקודות בעלות אותה קואורדינטת \(x\) או אותה קואורדינטת \(y\). הנחה זו אינה מציאותית, מכיוון ששדות בטבלה עשויים לייצג ערכים בעלי מספר קטן של אפשרויות, כמו גיל או תאריך, ולכן סביר שיהיו נקודות רבות בעלות ערכים זהים באותה קואורדינטה. למרבה המזל, הכללת מבני הנתונים שראינו עבור קלט כללי היא לא משימה קשה, וניתן לעשות זאת על ידי בחירה של סדר לקסיקוגרפי מסוים על הנקודות. תוכלו לקרוא על כך בסעיף 5.5 בספר הלימוד.