יחידה 8 מערכים ודואליות
8.1 הקדמה
8.1.2 דגימה גיאומטרית טובה
ההתמודדות עם נתוני עתק (big data) מציבה אתגר עצום בתחום טכנולוגית המידע, ואחת הדרכים להתמודד עם היקף מאסיבי של נתונים היא על ידי דגימה (sampling). למשל, בהינתן אוסף גדול מאוד של נקודות, ניתן לדגום מתוכן אוסף קטן יותר שישמש ייצוג קומפקטי של האוסף המקורי, ועליו ניתן לבצע חישובים ביעילות. גם כאשר רוצים למדל אובייקט רציף במחשב, משתמשים בדרך כלל באוסף סופי של נקודות או פיקסלים; למשל, כדי לייצג את פני השטח במפה טופוגרפית, לוקחים מדידות של גובה בנקודות אקראיות (האיור למטה לקוח מהמאמר הזה, ומציג מפה טופוגרפית של אזור הררי באסיה, עם 2,500 נקודות שנבחרו בדגימה מקרית).
הבחירה בדגימה מקרית של נקודות לעומת דגימה תבניתית יכולה לנבוע מכמה סיבות:
- דגימה מקרית מאפשרת הוכחה של חסמים הסתברותיים (חסמים על התוחלת).
- לפעמים דגימה מקרית נראית טבעית יותר לעין האנושית.
עם זאת, לא כל דגימה מקרית תהיה “טובה”, כלומר היינו רוצים שפיזור הנקודות שנדגמו יהיה פחות או יותר אחיד, כדי שישקף את המצב המקורי. נסביר זאת בסעיף הבא בעזרת מושג שנקרא discrepancy.
8.1.3 ה-discrepancy של קבוצת נקודות
נניח שדגמנו קבוצה \(S\) של \(n\) נקודות מריבוע היחידה \(U=[0,1]\times [0,1]\). היינו רוצים שלקבוצה \(S\) תהיה התכונה הבאה: לכל חצי מישור \(h\), שיעור הנקודות מ-\(S\) שנמצאות ב-\(h\) יהיה פחות או יותר כמו גודל החיתוך של \(h\) עם \(U\).
באופן פורמלי יותר, נגדיר את המדד הרציף של \(h\) להיות השטח של \(h \cap U\). נסמן אותו ב-\(\mu(h)\). נוסף על כך, נגדיר את המדד הדיסקרטי של \(h\) להיות \(\mu_S(h)=|S\cap h|/|S|\). הדגימה \(S\) תהיה טובה אם לכל בחירה של חצי מישור \(h\) יתקיים \(\mu(h)\approx\mu_S(h)\).
במתמטיקה, מושג זה נקרא Discrepancy. מדד ה-discrepancy של חצי המישור \(h\) מוגדר להיות: \[\Delta_S(h)=|\mu(h)-\mu_S(h)|.\]
דוגמה:
באיור משמאל, הקבוצה \(S\) מכילה חמש נקודות. חצי המישור \(h\) מכיל רק שתי נקודות מתוך \(S\), ולכן המדד הדיסקרטי של \(h\) הוא \(\mu_S(h)=|S\cap h|/|S|=2/5\). שטח החיתוך של חצי המישור \(h\) עם ריבוע היחידה \(U\) הוא בדיוק \(1/2\), ולכן מדד ה-discrepancy של \(h\) הוא \[\Delta_S(h)=|\mu(h)-\mu_S(h)|=|1/2-2/5|=1/10.\]
הגדרה: מדד ה-discrepancy של קבוצת נקודות
נסמן ב-\(\mathcal{H}\) את אוסף כל חצאי המישורים. מדד ה-discrepancy של הקבוצה \(S\) ביחס לחצאי מישור מוגדר להיות: \[\Delta_S(\mathcal{H})=\sup_{h\in\mathcal{H}}\Delta_S(h).\]
במילים אחרות, זהו חצי המישור ה”גרוע ביותר”, כלומר זה שעבורו מדד ה-discrepancy הוא מקסימלי. אינטואיטיבית, ככל שמדד ה-discrepancy מתקרב ל-0, כך הדגימה \(S\) טובה יותר, כלומר מפוזרת באופן אחיד יותר על פני \(U\).
(הערה: בסעיף 8.1 בספר הלימוד, הסימון למדד ה-discrepancy של קבוצה \(S\) ביחס לחצאי מישור הוא \(\Delta_\mathcal{H}(S)\), אך זוהי ככל הנראה שגיאת דפוס.)
ענו על השאלה הבאה:
התבוננו באיור הבא שבו מופיעה קבוצה \(S\) של נקודות (כחולות) בתוך ריבוע היחידה \(U\), וחצי מישור \(h\).
- מהו המדד הדיסקרטי של \(h\)?
- מהו המדד הרציף של \(h\)?
- מהו \(\Delta_S(h)\)?
- האם יש חצי מישור שהוא “גרוע יותר” מ-\(h\)? כלומר מדד ה-discrepancy שלו גדול יותר?
(פתרון)
הקבוצה \(S\) מכילה 12 נקודות. חצי המישור \(h\) מכיל שמונה מהן, ולכן המדד הדיסקרטי הוא \(8/12=2/3\).
שטח החיתוך של \(h\) עם \(U\) הוא \(1/2+1/8=5/8\) (ניתן לראות שהוא מכיל את שתי השורות התחתונות של הגריד, כלומר החצי התחתון של ריבוע היחידה, ועוד חצי מהשורה השלישית מלמטה).
באופן כללי, ניתן לחשב את השטח על ידי מציאת נקודות החיתוך של הישר המגדיר את חצי המישור \(h\) עם ריבוע היחידה, ואז לחשב את השטח כסכום של שטח מלבן ושטח משולש. קיבלנו \(\Delta_S(h)=2/3-5/8=1/24\).
שימו לב שקיימים מספר חצאי מישורים שלא מכילים אף נקודה כחולה, ושטח החיתוך שלהם עם הריבוע גדול מ-\(1/24\). לכן חצאי מישורים אלו “גרועים יותר” מ-\(h\).
8.1.4 חישוב ה-discrepancy של קבוצת נקודות
עכשיו נוכל לשאול: כיצד ניתן לחשב את \(\Delta_S(\mathcal{H})\)?
בעצם אנחנו מחפשים חצי מישור \(\hat{h}\) שעבורו \(\Delta_S(\mathcal{H})=\Delta_S(\hat{h})\) , כלומר לכל \(h\in\mathcal{H}\) מתקיים \(\Delta_S(\hat{h})\ge \Delta_S(h)\).
אבחנה מיידית ראשונה היא שהישר שמגדיר את \(\hat{h}\) חייב לעבור דרך לפחות נקודה אחת מ-\(S\): אם זה לא המצב, נוכל להזיז מעט את הישר המגדיר את \(\hat{h}\) לעבר הנקודה הקרובה ביותר אליו מאחד הצדדים, מבלי לשנות את המידה הדיסקרטית שלו. המידה הרציפה תגדל או תקטן, ובאחד הצדדים נקבל מדד discrepancy גדול יותר.
המועמדים להיות \(\hat{h}\)
כדי לחשב את \(\Delta_S(\mathcal{H})\), היינו רוצים למצוא מספר סופי של מועמדים להיות \(\hat{h}\). בסעיף 8.1 בספר הלימוד מוכיחים את הטענה הבאה:
*טענה (8.1 בספר הלימוד)**:
חצי מישור \(h\) שעבורו \(\Delta_S(h)\) מקסימלי, הוא אחד משני הסוגים הבאים:
- ל-\(h\) יש בדיוק נקודה אחת מ-\(S\) על שפתו,
- ל-\(h\) יש לפחות 2 נקודות על שפתו.
נוסף על כך, מספר המועמדים מהסוג הראשון הוא \(O(n)\), וניתן למצוא אותם בזמן \(O(n)\).
בהינתן מועמד \(h\), נוכל לחשב את המידה הרציפה שלו בזמן קבוע, ואת המידה הדיסקרטית שלו בזמן \(O(n)\). מכיוון שמספר המועמדים מהסוג הראשון הוא \(O(n)\) וגם ניתן למצוא אותם בזמן \(O(n)\), סך כל הזמן שייקח לנו לחשב את \(\Delta_S(h)\) עבור כל המועמדים מסוג זה הוא \(O(n^2)\).
מה בנוגע למועמדים מהסוג השני? מכיוון שיש \(O(n^2)\) כאלה, נצטרך לבצע את חישוב המידה הדיסקרטית שלהם באופן אחר. בהמשך היחידה נלמד טכניקה חשובה ומרתקת שתאפשר לנו לעשות זאת בזמן \(O(n^2)\) בסך הכול! לטכניקה הזו קוראים דואליות של נקודה וישר.
הערה: ביחידה זו נדלג על ההקדמה לפרק 8 בספר הלימוד, וכן על סעיף 8.1. כמו כן, לא נוכיח את הטענה שלעיל, ורק נראה כיצד ניתן להשתמש בה כדי לחשב את ה-discrepancy.
ענו על השאלה הבאה:
באיור למטה מופיעים ארבעה חצאי מישור, \(h_1,h_2,h_3,h_4\), כולם עוברים דרך אותה נקודה מ-\(S\). שימו לב ש-\(h_i\) מתקבל מ-\(h_{i-1}\) על ידי סיבוב של הישר המגדיר אותו נגד כיוון השעון. כל חצאי המישורים מכילים בדיוק את אותה קבוצת נקודות מ-\(S\). למי מהם \(\Delta_S\) מקסימלי? למי מינימלי?
(פתרון)
שטח החיתוך של \(h_1\) או \(h_2\) עם \(U\) הוא הגדול ביותר, והוא שווה ל-\(3/4\). השטח קטן יותר ויותר לאחר שעוברים את \(h_2\) ומסובבים לכיוון \(h_4\). שטח החיתוך של \(h_4\) עם \(U\) הוא הקטן ביותר. כולם מכילים \(4/5\) מהנקודות ב-\(S\), ולכן ככל ששטח החיתוך קטן נקבל הפרש גדול יותר בין המדד הדיסקרטי לרציף. לכן המדד המקסימלי יתקבל עבור \(h_1\) ו-\(h_2\), והמינימלי עבור \(h_4\).
8.2 דואליות של נקודה וישר
8.2.1 הגדרת הטרנספורמציה הדואלית
ביחידה 3 דיברנו על הגרף הדואלי לשילוש, וראינו שבעזרתו ניתן לחשב בקלות צביעה חוקית של קודקודי המשולשים בשלושה צבעים (שימו לב שניתן להגדיר באופן דומה גרף דואלי לגרף מישורי שפאותיו הן לא בהכרח משולשים). באופן כללי, דואליות היא כלי חשוב בניתוח ופתרון של בעיות גיאומטריות: היא מאפשרת לנו להסתכל על בעיה נתונה מפרספקטיבה שונה, על ידי תיאור של בעיה דואלית שקולה. לפעמים הבעיה הדואלית נראית פשוטה הרבה יותר לפתרון, ואז ניתן להפוך את הפתרון לבעיה הדואלית לפתרון לבעיה המקורית.
ביחידה זו נדבר על הדואליות של נקודות וישרים במישור. נקודה \(p\) במישור מתוארת על ידי שתי הקואורדינטות שלה, למשל, \(p=(p_x,p_y)\). גם ישר (לא אנכי) \(y=mx+b\) מתואר על ידי שני פרמטרים: השיפוע שלו, \(m\), והגורם הקבוע, \(b\). לכן ניתן למפות נקודה לישר, ולהפך, באופן חד-חד-ערכי. ניתן לחשוב על טרנספורמציות שונות, אך בקורס הזה נעסוק בטרנספורמציה הפשוטה הבאה.
הגדרה: הטרנספורמציה הדואלית
- הישר הדואלי לנקודה \(p=(p_x,p_y)\) יסומן ב-\(p^*\). והוא: \(p^*:~ y=p_x x-p_y\)
- הנקודה הדואלית לישר \(\ell:~ y=mx+b\) תסומן \(\ell^*\). והיא: \(\ell^*=(m,-b)\)
דוגמה:
- הישר הדואלי לנקודה \(p=(3,1)\) הוא \(p^*:~ y=3x-1\).
- הנקודה הדואלית לישר \(\ell:~ y=x+2\) היא \(\ell^*=(1,-2)\).
תכונות הטרנספורמציה – נסו בעצמכם!
הטרנספורמציה הדואלית שהגדרנו ממפה אובייקטים מהמישור הראשי (primal plane) למישור הדואלי (dual plane), ויש לה מספר תכונות מעניינות, שאותן נראה מייד. אך לפני כן, נסו לבחון בעצמכם את תכונות הטרנספורמציה הדואלית בעזרת היישומון הבא.
ענו על השאלה הבאה:
התבוננו באיור הבא, והתאימו בין נקודה לישר הדואלי שלה.
(פתרון)
זיכרו שקואורדינטת ה-\(x\) ממופה לשיפוע הישר, וקואורדינטת ה-\(y\) לחיתוך עם ציר ה-\(y\).
הנקודה \(p_1\) נמצאת על ציר ה-\(y\), כלומר קואורדינטת ה-\(x\) שלה היא אפס, ולכן לישר הדואלי המתאים לה יהיה שיפוע 0, כלומר זהו \(\ell_3\).
הנקודה \(p_2\) נמצאת על ציר ה-\(x\), כלומר קואורדינטת ה-\(y\) שלה היא אפס, ולכן הישר הדואלי המתאים לה ייחתך עם ציר ה-\(y\) בראשית הצירים, ולכן זהו \(\ell_1\).
עבור הנקודה \(p_3\) נשאר לנו הישר \(\ell_2\), אבל אפשר לזהות זאת גם ללא אלימינציה: לנקודה \(p_3\) קואורדינטת \(x\) חיובית וקואורדינטת \(y\) שלילית, ואכן השיפוע של \(\ell_2\) חיובי, והוא נחתך עם ציר ה-\(y\) מעל הראשית.
8.2.2 תכונות הטרנספורמציה הדואלית
כדי שנוכל להשתמש בטרנספורמציה הדואלית שהגדרנו, ננסה להבין תחילה מה היחס בין המישור הדואלי למישור הראשי, כלומר אילו תכונות נשמרות וכיצד. בסרטון הבא נבחן יחד את הטרנספורמציה הדואלית ואת התכונות שלה.
צפו בסרטון הבא:
בסרטון ראינו את האבחנה הבאה לגבי תכונות הטרנספורמציה הדואלית.
אבחנה (8.3 בספר הלימוד):
תהי \(p\) נקודה ו-\(\ell\) ישר לא אנכי, שניהם במישור. הטרנספורמציה הדואלית \(o\rightarrow o^*\) מקיימת את התכונות הבאות:
- משמרת יחס חילה (incidence preserving): \(p\in \ell\) אם ורק אם \(\ell^*\in p*\).
- משמרת סדר (order preserving): \(p\) מעל \(\ell\) אם ורק אם \(\ell^*\) מעל \(p^*\).
קטע במישור הדואלי – נסו בעצמכם!
ראינו שבמישור הדואלי, קטע \(s=\overline{pq}\) הוא איחוד הישרים הדואליים לנקודות על \(s\). כלומר \(s^*\) הוא אוסף אינסופי של ישרים, שלכולם נקודת חיתוך אחת. ניתן לראות זאת ביישומון הבא: הזיזו את הנקודה השחורה שעל הקטע \(\overline{pq}\), ותוכלו לראות כיצד הישר הדואלי (הצבוע בשחור) משתנה ביחס לישרים הדואלים ל-\(p\) ו-\(q\).
ענו על השאלה הבאה:
מהו האובייקט הדואלי ל-:
- \(k\) נקודות שכולן על ישר אחד (לא אנכי)?
- \(k\) ישרים מקבילים?
- חצי המישור שמעל ישר (לא אנכי)?
(פתרון)
- נניח שהנקודות \(p_1,\dots,p_k\) נמצאות כולן על ישר \(\ell\) במישור הראשי. מכאן שבמישור הדואלי, הנקודה \(\ell^*\) נמצאת על הישרים \(p_1,\dots,p_k\). כלומר הטרנספורמציה הדואלית של אוסף נקודות שנמצאות על ישר אחד היא אוסף של ישרים הנחתכים כולם באותה נקודה.
- נניח שהישרים \(\ell_1,\dots,\ell_k\) מקבילים. אז לכולם אותו שיפוע \(a\). לכן במישור הדואלי כל נקודה דואלית \(\ell^*_i\) היא מהצורה \((a,b_i)\), כלומר כל הנקודות הדואליות נמצאות על אותו ישר אנכי, \(x=a\).
- נסמן ב-\(\ell\) את הישר המגדיר את חצי המישור \(h\). במישור הראשי, כל נקודה \(p\) ב-\(h\) נמצאת מעל \(\ell\), ולכן במישור הדואלי, הנקודה \(\ell^*\) נמצאת מעל הישר \(p^*\). כלומר הטרנספורמציה הדואלית של חצי מישור היא אוסף הישרים שעוברים מתחת לנקודה.
הגדרה שקולה
בסעיף 8.2 בספר הלימוד מתוארת דרך אחרת לחשוב על הטרנספורמציה הדואלית – בעזרת הפרבולה \(\mathcal{U}:~ y=x^2/2\). עבור נקודה \(p\) שנמצאת על הפרבולה, הישר הדואלי \(p^*\) הוא בדיוק הישר המשיק לפרבולה בנקודה \(p\). עבור נקודה \(q\) שלא נמצאת על הפרבולה, ושיש לה אותה קואורדינטת \(x\) כמו ל-\(p\), השיפוע של \(q^*\) הוא בדיוק השיפוע של \(p^*\), אך \(q^*\) מוזז לפי ההפרש בקואורדינטת ה-\(y\). כלומר \(q^*\) הוא הישר המקביל ל-\(p^*\) ועובר דרך נקודה \(q'\), שהיא תמונת מראה של \(q\) ביחס לישר האופקי העובר דרך \(p\). תוכלו לראות את הקשר הזה בעזרת היישומון הבא.
8.3 מערכים של ישרים במישור
8.3.1 מערך של ישרים במישור: מבנה וגודל
קבוצה \(L\) של \(n\) ישרים במישור מחלקת את המישור לאוסף של תאים (פאות), צלעות וקודקודים. חלוקה כזאת של המישור נקראת מערך של ישרים (line arrangement), ומסומנת \(\mathcal{A}(L)\). בסרטון הבא נדבר על המבנה ועל הגודל של מערכי ישרים במישור.
צפו בסרטון הבא:
ראינו שלמערך \(\mathcal{A}(L)\) של ישרים במישור יש שלושה סוגי רכיבים:
- קודקודים – כאשר כל קודקוד הוא נקודת חיתוך בין ישרים מ-\(L\).
- צלעות – כאשר כל צלע היא קטע (פתוח) או קרן (שצידה האחד פתוח וצידה שני לא חסום) על אחד הישרים.
- פאות – כאשר כל פאה היא רכיב קשיר מקסימלי של נקודות שלא נמצאות על אחד הישרים.
הפאות הן כמובן קמורות, שכן הן נוצרות מחיתוך של חצאי מישורים.
כמו כן, הגדרנו שהמערך \(\mathcal{A}(L)\) הוא פשוט אם אין ב-\(L\) שלושה ישרים שעוברים דרך אותה נקודה, ואין ישרים מקבילים.
משפט (8.4 בספר הלימוד):
תהי \(L\) קבוצה של \(n\) ישרים במישור, ויהי \(\mathcal{A}(L)\) המערך של \(L\). מתקיים:
- מספר הקודקודים ב-\(\mathcal{A}(L)\) הוא לכל היותר \(n(n-1)/2\).
- מספר הצלעות ב-\(\mathcal{A}(L)\) הוא לכל היותר \(n^2\).
- מספר הפאות ב-\(\mathcal{A}(L)\) הוא לכל היותר \(n^2/2+n/2+1\).
כמו כן, מתקיים שוויון בכל השלושה אם ורק אם \(\mathcal{A}(L)\) הוא מערך פשוט.
8.3.2 ייצוג ובניית המערך
בעמוד הקודם ראינו שהמערך \(\mathcal{A}(L)\) של אוסף \(L\) של ישרים הוא חלוקה של המישור, ואסימפטוטית הוא לכל היותר מגודל ריבועי (במספר הישרים).
כיצד נייצג מערך של ישרים?
נוכל להשתמש במבנה DCEL שראינו ביחידה 2, שיאפשר לנו לעבור מפאה לפאה, לגשת לרשימת כל הצלעות שמגדירות פאה נתונה, ועוד. שימו לב שהמערך \(\mathcal{A}(L)\) מכיל גם צלעות אינסופיות, ולכן כדי להשתמש במבנה DCEL נצטרך להשתמש בטריק שכבר ראינו בעבר: נמצא מלבן \(R\) מספיק גדול שמכיל את כל הקודקודים של \(\mathcal{A}(L)\) בפנימו.
8.3.3 רמה (level) של נקודה במערך
לפני שנוכל לחזור לפתרון בעיית חישוב ה-discrepancy, נגדיר מונח נוסף שיעזור לנו במשימה הזאת (ובעוד רבות אחרות).
הגדרה: רמה של נקודה במערך של ישרים
הרמה (level) של נקודה \(r\) במערך של ישרים היא מספר הישרים שעוברים מעל \(r\) (מעל ממש, כלומר לא עוברים דרך \(r\)).
דוגמה:
הרמה של הנקודה \(p\) היא 3, מכיוון שעוברים מעליה שלושה ישרים: \(\ell_1,\ell_4,\ell_5\).
מהי הרמה של הנקודה \(q\)? שימו לב ש-\(q\) היא קודקוד של מערך הישרים, ורק הישר \(\ell_4\) עובר מעליה. לכן הרמה של \(q\) היא 1.
כיצד נוכל לחשב את הרמה של קודקוד במערך ישרים?
בהינתן מבנה DCEL של המערך \(\mathcal{A}(L)\), נוכל לחשב את הרמות של כל הקודקודים במערך בזמן \(O(n^2)\) בסך הכול, בעזרת האלגוריתם הבא.
עבור ישר \(\ell\in L\) כלשהו, נמצא את הקודקוד השמאלי ביותר שנמצא עליו, \(v_1\), ונחשב את הרמה שלו, \(level(v_1)\), בזמן \(O(n)\) על ידי בדיקת כל הישרים האחרים. לאחר מכן, נוכל להתקדם לאורך הישר \(\ell\) בעזרת מבנה ה-DCEL מהקודקוד הנוכחי, \(v_i\), אל הקודקוד שמימינו, \(v_{i+1}\), ולחשב את הרמה של \(v_{i+1}\) בהינתן \(level(v_i)\) בזמן קבוע:
- נאתחל \(level(v_{i+1})\leftarrow level(v_i)\).
- אם הישר דרך \(v_i\) עובר מעל \(v_{i+1}\), נוסיף 1 ל-\(level(v_{i+1})\).
- אם הישר דרך \(v_{i+1}\) עובר מעל \(v_i\), נחסיר 1 מ-\(level(v_{i+1})\).
(שימו לב ש-2 ו-3 יכולים להתקיים יחד, ואז הרמה של \(v_{i+1}\) לא תשתנה).
8.3.4 הכוח של דואליות
נחזור לבעית חישוב ה-discrepancy של קבוצת נקודות. בהינתן קבוצה \(S\) של \(n\) נקודות, המטרה שלנו בסוף החלק הראשון של יחידה זו הייתה לחשב לכל זוג נקודות \(p,q\in S\) את המדד הדיסקרטי של חצי המישור שחסום על ידי הישר \(\ell(p,q)\) העובר דרך \(p\) ו-\(q\). במישור הדואלי, הנקודה \(\ell(p,q)^*\) (הדואלית לישר \(\ell(p,q)\)) היא נקודת החיתוך בין \(p^*\) (הישר הדואלי ל-\(p\)), ל-\(q^*\) (הישר הדואלי ל-\(q\)). לכן נקודה \(s\) נמצאת מתחת לישר \(\ell(p,q)\) במישור הראשי, אם ורק אם הישר \(s^*\) עובר מתחת לנקודה \(\ell(p,q)^*\) במישור הדואלי.
שימו לב שבמישור הדואלי, \(S\) היא קבוצה \(S^*\) של ישרים, שמהווה מערך של ישרים. מכאן, שמספר הנקודות מ-\(S\) שנמצאות בחצי המישור הפתוח שמוגדר על ידי \(\ell(p,q)\) ונמצא מתחתיו, שווה למספר הישרים במישור הדואלי שעוברים מעל הנקודה \(\ell(p,q)^*\). זוהי בדיוק הרמה של הקודקוד \(\ell(p,q)^*\) במערך הישרים \(\mathcal{A}(S^*)\).
כמו שראינו בחלק הקודם, ניתן לחשב את הרמות של כל הקודקודים במערך ישרים בזמן \(O(n^2)\), ולכן נוכל לחשב את ה-discrepancy של \(S\) בזמן \(O(n^2)\).
8.4 תרגילים נוספים
תרגיל
תארו אלגוריתם שבהינתן אוסף \(L\) של \(n\) ישרים במישור, מוצא בזמן \(O(n\log n)\) מלבן \(R\) שמכיל את כל הקודקודים של \(\mathcal{A}(L)\) בפנימו.
תרגיל
נתון אוסף \(C\) של \(n\) מעגלים במישור. שימו לב שגם אוסף זה מהווה חלוקה של המישור לתאים. הצלעות במערך המעגלים יהיו קשתות של מעגלים מ-\(C\). שימו לב שהפאות במערך המעגלים אינן בהכרח קמורות. מהי הסיבוכיות של מערך מעגלים?
תרגיל
כפי שראיתם, בבעיות רבות בגיאומטריה חישובית אנחנו מניחים (לשם פשטות) שהקלט אינו מכיל שלוש נקודות הנמצאות על ישר אחד. כיצד ניתן לוודא זאת? בדיקה זו נקראת בדיקת קו-ליניארית, ואלגוריתם נאיבי יבדוק כל שלוש נקודות, בזמן של \(O(n^3)\). חשבו כיצד ניתן להשתמש ברעיון הדואליות כדי לבדוק זאת בזמן \(O(n^2)\) בלבד.