יחידה 9 שילושי דלוני
9.1 הקדמה
9.1.1 מה ביחידה?
שילושי דלוני
יחידה זו מקבילה לפרק התשיעי בספר הלימוד.
בסיום יחידה זו, תכירו את המושגים ותרכשו את הטכניקות והכלים הבאים:
- מפה מישורית מקסימלית.
- שילוש של קבוצת נקודות במישור.
- שילוש חוקי ושילוש אופטימלי בזוויות.
- גרף דלוני ושילוש דלוני.
- אלגוריתמים לחישוב השילוש (אלגוריתם היפוך צלעות, אלגוריתם סורק, אלגוריתם אינקרמנטלי-רנדומי).
למידה מהנה!
9.1.2 אינטרפולציה של גבהים
ייצוג תלת-ממדי של פני שטח (terrain) נעשה בדרך כלל על ידי לקיחה דגימות של גובה בנקודות מסוימות, וקביעת גובה הנקודות שלא נמדדו על ידי אינטרפולציה כלשהי של נקודות הדגימה. הדרך המקובלת לעשות זאת היא בעזרת שילוש של קבוצת הנקודות, כלומר חלוקה של המישור שכל הפאות החסומות שלה הן משולשים שקודקודיהם הם נקודות הדגימה. הגובה של נקודה \(q\) שלא נמדדה יתקבל כך: נמצא את המשולש \(\triangle abc\) שהנקודה \(q\) נמצאת בתוכו. הנקודות \(a,b,c\) עם מדידות הגובה שלהן הן נקודות תלת-ממדיות, ולכן מגדירות מישור בתלת-ממד. נטיל את \(q\) על המישור הזה, וקואורדינטת ה-\(z\) שתתקבל תהיה הגובה של \(q\).
לא כל השילושים ייראו לנו “טובים” או “טבעיים” באותה המידה. התבוננו למשל בשני השילושים באיור למטה. אלו שני שילושים שונים של אותה קבוצת נקודות, יחד עם הגבהים המתאימים להן. בכל אחד מהם, הנקודה המסומנת \(q\) תהיה בגובה שונה. איזה מהשילושים סביר שיתאר את המציאות באופן מהימן יותר?
ענו על השאלה הבאה:
מה (בערך) יהיה הגובה של הנקודה \(q\) בכל אחד מהשילושים באיור למעלה?
(פתרון)
בשילוש מימין, הגובה של \(q\) יהיה בין 100 ל-120. בשילוש משמאל, הגובה יהיה בין 550 ל-610.
השילוש משמאל נראה טבעי יותר מהימני, מכיוון שבאופן אינטואיטיבי סביר יותר שהגובה של הנקודה \(q\) יהיה דומה לגובה של הנקודות שנמצאות בסביבתה הקרובה.
ביחידה זו ננסה להבין כיצד להגדיר שילוש שמשקף את התפיסה האינטואיטיבית שלנו לגבי מהו שילוש “טוב”, וכן נלמד כיצד ניתן לחשב שילוש כזה.
9.2 שילוש של קבוצת נקודות במישור
9.2.1 מפה מישורית מקסימלית
ביחידה 3 בקורס דיברנו על שילוש של פוליגונים – חלוקה של פוליגון למשולשים על ידי מספר מקסימלי של אלכסונים שאינם חותכים זה את זה. ביחידה זו, נעסוק בשילושים של קבוצות של נקודות במישור. כדי להגדיר באופן פורמלי מהו שילוש של קבוצת נקודות, נסביר קודם מהי מפה מישורית מקסימלית (שימו לב שביחידה 2 עסקנו במפות מישוריות שאינן בהכרח מקסימליות).
הגדרה: מפה מישורית מקסימלית
מפה מישורית מקסימלית היא מפה מישורית שלא ניתן להוסיף לה צלעות, כלומר כל צלע שנוסיף בין שני קודקודים תחתוך צלע אחרת.
תכונות של מפה מישורית מקסימלית
כאשר פתרתם את התרגיל הקודם, ודאי הבחנתם בשתי התכונות הבאות:
הפאות (החסומות) הן משולשים: אם יש פאה חסומה שהיא לא משולש, ניתן לשלש אותה על ידי הוספת אלכסונים, כפי שראינו ביחידה 3 (שילוש של פוליגונים).
כל צלעות הקמור של קבוצת הקודקודים שייכות למפה (והן הצלעות של הפאה הלא חסומה): לא תיתכן צלע שיוצאת החוצה מהקמור, ולכן הצלעות של הקמור לא יחתכו שום צלע אחרת, ויהיה ניתן להוסיף אותן למפה.
9.2.2 שילוש של נקודות במישור
התכונה הראשונה שראינו מובילה אותנו להגדרת שילוש של קבוצת נקודות \(P\) במישור באופן הבא:
הגדרה: שילוש של קבוצת נקודות במישור
בהינתן קבוצה \(P\) של \(n\) נקודות במישור, שילוש של \(P\) הוא מפה מישורית מקסימלית שהקודקודים שלה הם נקודות \(P\).
שימו לב, ייתכן שקיים יותר משילוש אחד לקבוצה נתונה של נקודות!
ענו על השאלה הבאה:
כמה שילושים שונים תוכלו למצוא עבור קבוצת הנקודות הבאה? כמה משולשים יש בכל אחד מהשילושים?
(פתרון)
זכרו שצלעות הקמור חייבות להיות בשילוש. יש שלושה שילושים אפשריים, בכל אחד מהם ארבעה משולשים. מייד נראה שזה לא מקרי – כל השילושים האפשריים של קבוצת נקודות נתונה הם בדיוק באותו הגודל!
גודל השילוש
באופן מעניין למדי, כל השילושים האפשריים של קבוצה \(P\) של \(n\) נקודות הם בדיוק באותו הגודל, כלומר יש להם מספר זהה של משולשים וצלעות. גודל השילוש תלוי במספר הנקודות שמופיעות על השפה של \(CH(P)\) (שפת הקמור של \(P\)).
משפט (9.1 בספר הלימוד): תהי \(P\) קבוצה של \(n\) נקודות במישור, שלא כולן על ישר אחד. נסמן ב-\(k\) את מספר הנקודות על השפה של \(CH(P)\). לפיכך בכל שילוש של \(P\) יש \(2n-2-k\) משולשים ו-\(3n-3-k\) צלעות.
ההוכחה למשפט מופיעה בסעיף 9.1 בספר הלימוד, ונעשה בה שימוש בנוסחת אוילר, שכבר ראינו כמה פעמים בעבר.
9.2.3 שילוש חוקי ושילוש אופטימלי בזוויות
בהקדמה ליחידה זו, ראינו ששילושים שלא מכילים משולשים “צרים” (כלומר כאלו שיש להם זוויות חדות מאוד), בסבירות גבוהה משקפים טוב יותר את המצב במציאות. לכן נעדיף שילושים שבהם הזוויות הן כמה שיותר גדולות. בסרטון הבא נראה כיצד ניתן להגדיר שילוש אופטימלי כזה באופן מדויק.
9.2.4 חזרה: הגדרות ותרגילים
למטה מופיעות ההגדרות, האבחנות והטענות המרכזיות שדנו בהן בחלק זה, כדי שיהיה לכם נוח לחזור אליהן בעתיד. נוסף על כך, מופיעות כאן הערות ודוגמאות נוספות וכן תרגילים לחזרה, כך שמומלץ לעבור על כל אלו לפני שממשיכים לסעיף הבא.
הגדרה: וקטור הזוויות
בהינתן שילוש \(\mathcal{T}\) בעל \(m\) משולשים, נסמן את \(3m\) זוויות המשולשים שלו \(\alpha_1,\alpha_2,\dots,\alpha_{3m}\) כך ש-\(\alpha_i\le\alpha_j\) לכל \(i<j\). הווקטור \(A(\mathcal{T}):=(\alpha_1,\alpha_2,\dots,\alpha_{3m})\) נקרא וקטור הזוויות של \(\mathcal{T}\).
ענו על השאלה הבאה:
מהו וקטור הזוויות של השילוש \(\mathcal{T}\) הבא?
(פתרון)
\(A(\mathcal{T})=(20^\circ,30^\circ,40^\circ,45^\circ,110^\circ,115^\circ)\)
הגדרה: שילוש אופטימלי בזוויות
עבור שני שילושים שונים \(\mathcal{T}\) ו-\(\mathcal{T}'\) של אותה קבוצת נקודות, נגדיר שווקטור הזוויות \(A(\mathcal{T}):=(\alpha_1,\alpha_2,\dots,\alpha_{3m})\) גדול מווקטור הזוויות \(A(\mathcal{T}'):=(\alpha'_1,\alpha'_2,\dots,\alpha'_{3m})\) אם הוא גדול ממנו בסדר לקסיקוגרפי. כלומר \(A(\mathcal{T})>A(\mathcal{T}')\) אם קיים \(1\le i\le 3m\) כך ש־:
- \(\alpha_j=\alpha'_j\) לכל \(j<i\), וגם
- \(\alpha_i>\alpha'_i\).
שילוש \(\mathcal{T}\) הוא שילוש אופטימלי בזוויות אם לכל שילוש אחר \(\mathcal{T}'\) של אותה קבוצת נקודות מתקיים \(A(\mathcal{T})\ge A(\mathcal{T}')\).
ענו על השאלה הבאה:
איזה מהווקטורים הבאים גדול יותר בסדר לקסיקוגרפי?
\(A_1=(20^\circ,30^\circ,30^\circ,50^\circ, 120^\circ, 130^\circ)\)
או
\(A_2=(20^\circ,30^\circ,35^\circ,40^\circ, 90^\circ, 110^\circ)\)
(שימו לב שווקטורים אלו לא בהכרח מייצגים שילוש כלשהו.)
(פתרון)
\(A_2\)
משפט תאלס (מורחב) - נסו בעצמכם!
משפט (9.2 בספר הלימוד):
יהי \(C\) מעגל, ו-\(\ell\) ישר שחותך את המעגל בנקודות \(a,b\). יהיו \(p,q,s,r\) נקודות שכולן מאותו צד של \(\ell\), כך ש-\(p,q\) נמצאות על שפת המעגל, \(r\) בתוכו ו-\(s\) מחוץ למעגל. אז מתקיים: \[\measuredangle asb < \measuredangle apb = \measuredangle aqb < \measuredangle arb.\]
הערה לגבי המשפט(ים) של תאלס
קיימים כמה משפטים בגיאומטריה של המישור שנקראים באותו השם – “משפט תאלס”. אם למדתם גיאומטריה בתיכון בישראל, כנראה שאתם מכירים גרסה אחרת של המשפט. בוויקיפדיה גרסה זו נקראת המשפט השני.
פעולת היפוך צלע
יהי \(\mathcal{T}\) שילוש, ו-\(e=\overline{p_ip_j}\) צלע בשילוש שמשותפת לשני משולשים \(\triangle p_ip_jp_k\) ו- \(\triangle p_ip_jp_l\). אם המרובע \(p_ip_kp_jp_l\) הוא קמור אז ניתן לקבל מ-\(\mathcal{T}\) שילוש אחר, \(\mathcal{T}'\), על ידי החלפת הצלע \(e\) בצלע \(\overline{p_kp_l}\). פעולה זו נקראת היפוך של \(e\), או \(flip(e)\).
צלעות לא חוקיות
צלע \(\overline{p_ip_j}\) בשילוש \(\mathcal{T}\) שמשותפת לשני משולשים \(\triangle p_ip_jp_k\) ו- \(\triangle p_ip_jp_l\) היא לא חוקית אם ורק אם המעגל \(C\) שעובר דרך \(p_i,p_j,p_k\) מכיל את \(p_l\) בפנימו.
תמיד ניתן לבצע היפוך של צלע לא חוקית: אם \(\overline{p_ip_j}\) לא חוקית, אז המרובע \(p_ip_kp_jp_l\) חייב להיות קמור.
טענה (9.4 בספר הלימוד): אם המרובע \(p_ip_kp_jp_l\) הוא קמור, ואין מעגל שעובר דרך ארבע הפינות שלו, אז בדיוק אחד משני האלכסונים של המרובע הוא חוקי. אם קיים מעגל שעובר דרך ארבע הפינות שלו, אז שני האלכסונים חוקיים.
ענו על השאלה הבאה:
איזה מהאלכסונים של המרובע \(p_ip_kp_jp_l\) אינו חוקי?
(פתרון)
האלכסון \(p_lp_k\) אינו חוקי מכיוון שהמעגל הסגול שעובר בנקודות \(p_l,p_i,p_k\) מכיל את \(p_j\).
ענו על השאלות הבאות:
שאלה 1: התבוננו בשילוש הבא.
- האם הצלע \(p_2p_4\) חוקית?
- האם הצלע \(p_1p_4\) חוקית?
- האם יתקבל שילוש חוקי לאחר שנבצע \(flip(p_1p_4)\)?
(פתרון)
- כן.
- לא.
- לא, מכיוון שאז הצלע \(p_2p_4\) תהפוך ללא חוקית.
שאלה 2: נכון או לא נכון?
- כל שילוש אופטימלי בזוויות הוא חוקי.
- כל שילוש חוקי הוא אופטימלי בזוויות.
(פתרון)
- נכון. תמיד ניתן “לשפר” שילוש לא חוקי על ידי פעולת היפוך צלע. שילוש אופטימלי לא ניתן לשיפור, ולכן הוא חוקי.
- במצב לא כללי, כלומר כאשר יש ארבע נקודות על מעגל אחד, ייתכן שילוש חוקי שאינו אופטימלי בזוויות. שימו לב שבשילוש חוקי רק הזווית המינימלית היא חשובה, ולעומת זאת בשילוש אופטימלי בזוויות מתחשבים בכל וקטור הזוויות. בדוגמה הבאה מימין מופיע שילוש חוקי שאינו אופטימלי בזוויות, ומשמאל שילוש אופטימלי. שימו לב שווקטור הזוויות של שני השילושים כמעט זהה, פרט לכך שבשילוש מימין יש שתי זוויות שנשענות על האלכסון \(p_kp_l\), ובשילוש משמאל יש שתי זוויות שנשענות על האלכסון \(p_ipj\) שהוא ארוך יותר, ולכן זוויות אלו גדולות יותר.
בהמשך נראה שאם הנקודות במצב כללי (כלומר אין ארבע נקודות על מעגל אחד), אז כל שילוש חוקי הוא אופטימלי בזוויות.
9.3 שילוש דלוני
9.3.1 גרף דלוני ושילוש דלוני
לפני שנמשיך לדבר על שילושים, נציג את גרף דלוני, שהוא הגרף הדואלי לדיאגרמת וורונוי של קבוצת נקודות. מהן תכונות הגרף? וכיצד הוא קשור לשילוש? על כך בסרטון הבא.
צפו בסרטון הבא:
בסרטון הגדרנו את גרף דלוני \(\mathcal{DG}(P)\) של קבוצת נקודות \(P\) במישור, בעזרת דיאגרמת וורונוי של \(P\): זהו שיכון של הגרף הדואלי ל-\(Vor(P)\), שהקודקודים שלו הם נקודות \(P\), והצלעות הן הקטעים הישרים המחברים בין אתרים שלפאות שלהם בדיאגרמה יש צלע משותפת. הוכחנו שגרף דלוני הוא מישורי, ודיברנו על התכונות המאפיינות אותו.
ענו על השאלות הבאות:
שאלה 1: האם כל צלע של גרף דלוני חותכת את הצלע המשותפת לפאות של שני האתרים המתאימים לה בדיאגרמת וורונוי? אם כן, הסבירו. אם לא, ציירו דוגמה לכך.
(פתרון)
לא, דוגמה:
שאלה 2: כמה תאים של דיאגרמת וורונוי יכולים להיחתך עם אותה צלע של גרף דלוני במקרה הגרוע ביותר?
(פתרון)
במקרה הגרוע ביותר, צלע אחת של גרף דלוני יכולה להיחתך עם כל התאים. דוגמה:
תכונות של גרף דלוני
המשפט הבא מקביל לתכונות שראינו עבור דיאגרמת וורונוי:
משפט (9.6 בספר הלימוד): תהי \(P\) קבוצה של נקודות במישור.
- שלוש נקודות \(p_i,p_j,p_k\in P\) הן קודקודים של אותה פאה חסומה ב-\(\mathcal{DG}(P)\) אם ורק אם המעגל דרך \(p_i,p_j,p_k\) לא מכיל נקודות של \(P\) בפנימו.
- זוג נקודות \(p_i,p_j\in P\) יוצרות צלע של \(\mathcal{DG}(P)\) אם ורק אם קיים דיסק סגור \(C\) שמכיל את \(p_i,p_j\) על שפתו, ואינו מכיל עוד אף נקודה אחרת של \(P\).
ענו על השאלות הבאות:
שאלה 1: נתונה קבוצה \(P=\{p_1,p_2,p_3,p_4\}\) כך שכל ארבע הנקודות נמצאות על מעגל אחד. כיצד ייראה גרף דלוני של \(P\)?
(פתרון)
לפי התכונה הראשונה, כל הנקודות של \(P\) שייכות לאותה פאה חסומה, ונקבל גרף (ירוק באיור) עם פאה חסומה אחת שהיא מרובע שקודקודיו הם \(\{p_1,p_2,p_3,p_4\}\).
ניתן גם לראות זאת לפי דיאגרמת וורונוי: מרכז המעגל הוא קודקוד בדיאגרמת וורונוי, והוא משותף לכל הפאות, אך אין צלע משותפת לקודקודים “נגדיים”, כלומר כאלו המתאימים לאלכסונים של המרובע.
שאלה 2: האם פאה של גרף דלוני חייבת להיות קמורה? אם לא, ציירו דוגמה. אם כן, הסבירו.
(פתרון)
כן. לפי התכונה הראשונה, כל הקודקודים של פאה בגרף דלוני נמצאים על מעגל אחד, ומחוברים בצלעות לפי הסדר שלהם על המעגל. לכן כל הפאות בגרף דלוני הן קמורות.
שילוש דלוני
ראינו שגרף דלוני של קבוצת נקודות \(P\) אינו בהכרח שילוש: אם קיימות ארבע נקודות ב-\(P\) על מעגל אחד, נקבל פאה שאינה משולש. לעומת זאת, אם לא קיימות ארבע נקודות ב-\(P\) על מעגל אחד, אז כל הקודקודים של דיאגרמת וורונוי יהיו מדרגה 3, ולכן גרף דלוני יהיה שילוש. לכן בשלב זה נאמר שקבוצת נקודות \(P\) היא במצב כללי אם אין בה ארבע נקודות על מעגל אחד.
בכל זאת, לא נניח שהנקודות הן במצב כללי, ונגדיר את שילוש דלוני של קבוצת נקודות \(P\) להיות כל שילוש המתקבל על ידי הוספת צלעות ל-\(\mathcal{DG}(P)\).
9.3.2 וקטור הזוויות של שילוש דלוני
בסעיף 9.2 בספר הלימוד מוכיחים את המשפט הבא:
משפט (9.8 בספר הלימוד): שילוש \(\mathcal{T}\) של קבוצת נקודות \(P\) במישור הוא חוקי, אם ורק אם \(\mathcal{T}\) הוא שילוש דלוני של \(P\).
כיוון אחד של ההוכחה נובע מיידית מההגדרה ומהתכונות של שילוש דלוני: כל שילוש דלוני הוא חוקי, מכיוון שהמעגל החוסם של כל משולש ב-\(\mathcal{T}\) אינו מכיל נקודות של \(P\) בפנימו. הוכחת הכיוון השני היא מורכבת יותר, ומופיעה בספר הלימוד.
מתי שילוש דלוני הוא אופטימלי בזוויות?
כל שילוש אופטימלי הוא חוקי, ולכן הוא בהכרח שילוש דלוני! מתי שילוש דלוני הוא אופטימלי בזוויות?
אם הנקודות במצב כללי, אז שילוש דלוני הוא יחיד! לכן יש רק שילוש חוקי אחד, והוא השילוש האופטימלי היחיד.
אם הנקודות לא במצב כללי, אז שילוש דלוני לא בהכרח אופטימלי בזוויות. עם זאת, אפשר להראות (בעזרת משפט תאלס המורחב) שלכל שילוש דלוני יש בדיוק אותה זווית מינימלית (ההוכחה בסעיף 9.2 בספר הלימוד). לכן לכל השילושים החוקיים יש אותה זווית מינימלית, ובפרט זוהי גם הזווית המינימלית בשילוש אופטימלי. לכן הזווית המינימלית בשילוש דלוני היא המקסימלית האפשרית על פני כל השילושים של \(P\).
הדיאגרמה הבאה נועדה לעשות סדר בהגדרות השונות לסוגי שילושים שראינו עד כה. הקבוצה \(T_1\) מכילה את כל השילושים, \(T_2\) מכילה את כל השילושים שבהם הזווית המינימלית היא מקסימלית, \(T_3\) מכילה את כל השילושים החוקיים (שהם למעשה כל שילושי דלוני), \(T_4\) מכילה שילושים אופטימליים בזוויות.
9.4 חישוב השילוש
9.4.1 אלגוריתם שילוש נאיבי
מכיוון ששילוש דלוני שימושי מאוד ביישומים רבים ומגוונים, קיימים כמה אלגוריתמים שונים לחישובו. האלגוריתם הפשוט ביותר הוא זה שפגשתם בחלק האחרון של סעיף 9.1 בספר הלימוד. הוא מתחיל משילוש \(\mathcal{T}\) כלשהו, ואז, כל עוד קיימת צלע לא חוקית, הוא מבצע פעולת היפוך. מכיוון שבכל פעולת היפוך וקטור הזוויות של השילוש גדל (בסדר הלקסיקוגרפי), התהליך הוא סופי, ובסופו יתקבל שילוש אופטימלי בזוויות.
ענו על השאלה הבאה:
הפעילו את האלגוריתם הנאיבי על השילוש הבא, וציירו את השילוש האופטימלי שהתקבל. כמה פעולות היפוך צלע ביצע האלגוריתם?
(פתרון)
מייד נפגוש שני אלגוריתמים נוספים, לשניהם זמן ריצה \(O(n\log n)\) (לראשון במקרה הגרוע, לשני בתוחלת), אך הם שונים זה מזה בפשטות המימוש או ביעילות שלהם בפועל במצבים מסוימים (ראו למשל את המאמר הזה, המשווה בין הביצועים של האלגוריתמים השונים על אוספים של נקודות שנדגמו מהתפלגויות שונות).
9.4.2 אלגוריתם שילוש סורק (שימוש בדיאגרמת וורונוי)
מכיוון שגרף דלוני הוא הדואלי לדיאגרמת וורונוי, ניתן לחשב את שילוש דלוני של קבוצת נקודות \(P\) במישור בעזרת דיאגרמת וורונוי של \(P\):
- נחשב את \(Vor(P)\) בעזרת האלגוריתם הסורק שראינו ביחידה 7 (הדיאגרמה מופיעה בכחול באיור משמאל).
- נבנה את הגרף הדואלי לדיאגרמה, כלומר גרף דלוני (מופיע בירוק באיור).
- לבסוף, אם יש פאה בגרף שהיא לא משולש, נשלש אותה. נוכל לעשות זאת למשל בעזרת האלגוריתם לשילוש של פוליגון שראינו ביחידה 3. (באיור משמאל יש פאה אחת בגרף דלוני שהיא לא משולשת, ולכן נוסיף את הצלע האפורה).
זמן הריצה הכולל יהיה \(O(n\log n)\) (במקרה הגרוע).
9.4.3 אלגוריתם שילוש אינקרמנטלי-רנדומי
דרך אחרת לחישוב שילוש דלוני היא בעזרת האלגוריתם האינקרמנטלי-רנדומי DelaunayTriangulation המתואר בסעיף 9.3 בספר הלימוד.
הרעיון המרכזי באלגוריתם הוא לבנות משולש כלשהו, גדול מספיק, שמכיל את כל הנקודות של הקבוצה \(P\) בפנימו, ואז להוסיף את נקודות \(P\) בזו אחר זו, בסדר אקראי, ובכל פעם לעדכן את השילוש.
נסמן את נקודות \(P\) לפי הסדר האקראי ב-\(p_1,p_2,\dots,p_n\), ואת קודקודי המשולש ההתחלתי ב-\(p_{-1},p_{-2},p_{-3}\). נניח שחישבנו את שילוש דלוני של \(p_{-1},p_{-2},p_{-3},p_1,p_2,\dots,p_{r-1}\), ועכשיו אנחנו רוצים להוסיף את \(p_r\). יש שני מקרים:
- אם הנקודה \(p_r\) נמצאת בפנים של משולש \(\triangle p_ip_jp_k\): נוסיף צלעות מ-\(p_r\) לכל אחד מקודקודי המשולש.
- אם הנקודה \(p_r\) נמצאת על צלע \(\overline{p_ip_j}\) שמשותפת לשני משולשים, \(\triangle p_ip_jp_k\) ו-\(\triangle p_ip_jp_l\): נוסיף צלעות מ-\(p_r\) לקודקודים \(p_k\) ו-\(p_l\).
בשני המקרים קיבלנו שילוש, שהוא לא בהכרח שילוש דלוני. כדי לתקן את השילוש במקרה הצורך, האלגוריתם קורא לפרוצדורה נוספת בשם LegalizeEdge, שמקבלת שילוש, את הקודקוד \(p_r\), וצלע במשולש שייתכן שיש צורך לבצע פעולת היפוך עבורה. במקרה הראשון למשל, האלגוריתם יקרא לפרוצדורה הזאת עבור כל אחת מצלעות המשולש \(\triangle p_ip_jp_k\). אם הצלע אינה חוקית, הפרוצדורה תבצע היפוך שלה, ואז תמשיך לבדוק באופן רקורסיבי את צלעות המשולשים החדשים שנוצרו.
ענו על השאלה הבאה:
התבוננו באיור הבא, המתאר את השלב באלגוריתם שבו הנקודה \(p_r\) נוספה לשילוש, יחד עם צלעות לקודקודים \(p_1\), \(p_4\), ו-\(p_5\), ולפני הפעלת הפרוצדורה LegalizeEdge. כיצד ייראה השילוש לאחר הפעלת LegalizeEdge על כל אחת מצלעות המשולש \(\triangle p_1p_4p_5\)?
(פתרון)
פעולות ההיפוך שיתבצעו הן:
היפוך של \(p_1p_5\).
היפוך של \(p_1p_6\).
היפוך של \(p_1p_4\).
היפוך של \(p_2p_4\).
בסוף התהליך, יהיו צלעות מ-\(p_r\) לכל אחד מהקודקודים האחרים.
9.4.4 ניתוח האלגוריתם האינקרמנטלי-רנדומי
ניתוח זמן הריצה של האלגוריתם משתמש בטכניקה שכבר ראינו ביחידות 4 ו-6: אנליזה לאחור. ביחידה זו לא נתעמק בפרטי ההוכחה ונסתפק בציטוט המשפט הבא:
משפט (9.12 בספר הלימוד): האלגוריתם האינקרמנטלי-רנדומי מחשב שילוש דלוני של קבוצה \(P\) של \(n\) נקודות במישור בזמן \(O(n \log n)\) בתוחלת, ועם תוחלת זיכרון \(O(n)\).