TRIANGULATIONS

Report
TRIANGULATIONS - Part II
19.12.11 ‫אנה גלייזר‬
‫על מה נדבר היום‪:‬‬
‫• טריאנגולציות ‪DELAUNAY‬‬
‫• טריאנגולציות מיוחדות‪:‬‬
‫‪ ‬טריאנגולציה ממשקל מינימלי – ‪MWT‬‬
‫‪ ‬טריאנגולציות תואמות‬
‫‪ ‬פסאודו‪-‬טריאנגולציות‬
‫‪2‬‬
‫טריאנגולציות ‪DELAUNAY‬‬
‫‪3‬‬
‫המוטיבציה‪:‬‬
‫עבור אוסף נקודות דגימה ‪ S‬על המישור‬
‫(נקודות שמדדנו את גובהן)‬
‫נרצה לעשות שחזור של פני הקרקע כמה‬
‫שיותר קרוב למציאות‪ .‬נקודות הדגימה‬
‫מהוות אומדן לגובה הנקודות הסמוכות‬
‫(שגובהן לא נמדד)‬
‫‪4‬‬
‫נעשה זאת בעזרת טריאנגולציה‪:‬‬
‫נבצע טריאנגולציה על אוסף הנקודות‬
‫ואח"כ "נרים" כל משולש במישור‬
‫לגובהו המתאים וכך נקבל את אותו‬
‫המשולש בתלת‪-‬ממד‪.‬‬
‫שחזור פני הקרקע יורכב ממשולשים‬
‫אלה‪.‬‬
5
‫אך איזו טריאנגולציה הכי מתאימה לשחזור פני הקרקע‬
‫על סמך נקודות הדגימה בלבד?‬
‫כיוון שפני הקרקע האמיתיים אינם ידועים פרט לנקודות הנ"ל‪ ,‬אזי‬
‫לבחירת הטריאנגולציה תהיה השפעה רבה על מראה השחזור‪.‬‬
‫דוגמא‪:‬‬
‫‪6‬‬
‫איך נוכל לבחור בטריאנגולציה המתאימה ללא מידע נוסף?‬
‫הניסיון שלנו עם פני קרקע טבעיים נותן לנו אינטואיציה שמעבדת חלק‬
‫מהשחזורים בצורה "טבעית" יותר לעין האנושית‪.‬‬
‫דוגמא‪:‬‬
‫‪7‬‬
‫מה הופך את הטריאנגולציה השמאלית ליותר טבעית מהימנית?‬
‫הסיבה כנראה בגלל העובדה שההיפוך באיור הימני יצר‬
‫"משולשים רזים" ביחס למצב הקודם‪.‬‬
‫על כן‪ ,‬נעדיף טריאנגולציה שנמנעת ממשולשים רזים ע"י מקסום הזווית‬
‫הקטנה ביותר בכל משולש‪.‬‬
‫הערה‪:‬‬
‫מעתה נניח כי אוסף נקודות במצב כללי לא מכיל ‪ 4‬נקודות‬
‫על אותו מעגל‪.‬‬
‫סימון‪:‬‬
‫תהי ‪ T‬טריאנגולציה של אוסף הנקודות ‪ S‬כך ש‪ T -‬מכילה  משולשים‪.‬‬
‫אזי סדרת הזוויות ) ‪ (1 ,2 , … ,3‬של ‪ T‬היא רשימה ממוינת של ‪3‬‬
‫הזוויות של ‪ T‬מהזווית הקטנה ביותר ‪ 1‬לגדולה ביותר ‪.3‬‬
‫הערה‪:‬‬
‫ניזכר שמס' המשולשים בכל טריאנגולציה הוא קבוע ולכן אורכה של‬
‫סדרת הזוויות בכל טריאנגולציה זהה‪ .‬מכאן גם נובע כי סכום הזוויות‬
‫של הסדרה שווה בכל טריאנגולציה‪.‬‬
‫‪8‬‬
‫סימון‪:‬‬
‫בהינתן ‪ 2‬טריאנגולציות ‪ 1 ,2‬נאמר כי ‪ 1‬שמנה יותר מ‪2 -‬‬
‫(ונכתוב ‪ )1 > 2‬אם סדרת הזוויות של ‪ 1‬גדולה יותר‬
‫לקסיקוגרפית מזו של ‪.2‬‬
‫במילים אחרות‪ ,‬אם ) ‪ (1 ,2 , … ,3‬היא סדרת הזוויות של ‪1‬‬
‫ו‪ (1 ,2 , … ,3 ) -‬של ‪ ,2‬אזי קיים ‪ 1 ≤  ≤ 3‬כך שלכל  < ‬
‫מתקיים‪  =  :‬ו‪. >  -‬‬
‫לכן סדרת הזוויות ) ‪ (20° ,30° ,45° ,65° ,70° ,130°‬שמנה יותר מ‪-‬‬
‫) ‪.(20° ,30° ,45° ,60° ,75° ,130°‬‬
‫‪9‬‬
‫הגדרות‪:‬‬
‫‪ ‬תהי  צלע של טריאנגולציה ‪ 1‬ויהי ‪ Q‬מרובע ב‪ 1 -‬הנוצר ע"י‬
‫‪ 2‬משולשים ש‪  -‬היא צלע משותפת שלהם‪ .‬אם ‪ Q‬הוא קמור‪,‬‬
‫תהי ‪ 2‬טריאנגולציה לאחר היפוך ( ‪ ) flip‬הצלע  ב‪.1 -‬‬
‫נאמר כי  היא צלע חוקית אם ‪ 1 ≥ 2‬ו‪ -‬היא לא חוקית‬
‫אם ‪.1 < 2‬‬
‫הערה‪ :‬אם ‪ Q‬הוא לא קמור‪ ,‬אזי נתייחס אל  כאל צלע‬
‫חוקית‪.‬‬
‫‪10‬‬
‫‪ ‬עבור אוסף נקודות ‪ ,S‬נגדיר את טריאנגולציית ‪ Delaunay‬של ‪,S‬‬
‫המסומנת ע"י )(‪ ,‬להיות טריאנגולציה המכילה רק צלעות‬
‫חוקיות‪.‬‬
‫‪EDGE FLIPPING –Delaunay Triangulation Algorithm‬‬
‫יהי ‪ S‬אוסף נקודות במצב כללי (כלומר‪ ,‬ללא ‪ 4‬נקודות על אותו מעגל)‬
‫ותהי ‪ T‬טריאנגולציה התחלתית כשלהי‪.‬‬
‫אם ‪ T‬מכילה צלע לא חוקית‪ ,‬נבצע היפוך של הצלע ובכך היא תהפוך‬
‫להיות חוקית‪.‬‬
‫נמשיך לבצע היפוכי צלעות לא חוקיות‪ ,‬ע"י מעבר בסדר כלשהו בגרף‬
‫ההיפוכים של ‪ ,S‬עד שלא תהיינה עוד צלעות לא חוקיות‪.‬‬
‫‪11‬‬
‫הערה‪ :‬מכיוון שצלעות לא חוקיות עוברות היפוך‪ ,‬סדרת הזוויות של‬
‫הטריאנגולציה החדשה הולכת וגדלה‪ .‬ומכיוון שיש מס' סופי של‬
‫טריאנגולציות (מכיוון שיש מס' סופי של קודקודים)‪ ,‬אזי האלגוריתם‬
‫חייב להסתיים‪.‬‬
‫מבנייה נובע כי טריאנגולציית ‪ Delaunay‬החדשה תהיה גדולה יותר‬
‫מכל אחד מהשכנים שלה בגרף ההיפוכים‪.‬‬
‫תרגיל‪ :‬הוכח או הפרך ‪-‬‬
‫תחת האלגוריתם הנ"ל‪ ,‬ייתכן כי צלע חוקית תהפוך מאוחר יותר ללא חוקית‪.‬‬
‫פתרון‪:‬‬
‫נראה דוגמא לכך שזה נכון‪:‬‬
‫‪12‬‬
‫משפט ‪Thales‬‬
‫בהינתן ‪ 3‬נקודות ‪ ,Q ,P‬ו‪ B -‬על המעגל‪ ,‬נקודה ‪ A‬בתוך המעגל ונקודה ‪C‬‬
‫מחוצה לו‪ ,‬אזי הזווית ‪ PAQ‬גדולה יותר מ‪ ,PBQ -‬שגדולה יותר מ‪.PCQ -‬‬
‫דוגמא‪:‬‬
‫‪13‬‬
‫הוכחה‪:‬‬
‫נראה שהזווית ‪ PCQ‬קטנה יותר מ‪ :PBQ-‬נסמן את גודל הזווית ‪ PBQ‬ב‪. -‬‬
‫נסמן את נק' החיתוך של הקטע ‪ CQ‬עם המעגל ב‪ D -‬ונחבר את ‪ D‬עם ‪.P‬‬
‫כעת‪ ,‬מכיוון שהזווית שנוצרה ‪ PDQ‬נמצאת על אותה קשת כמו הזווית ‪ PBQ‬הרי‬
‫גם היא שווה ל‪ . -‬בנוסף‪ ,‬נשים לב שהזווית ‪ PDQ‬היא זווית חיצונית למשולש‬
‫‪ PCD‬ולכן גודלה שווה לסכום הזוויות ‪ PCQ‬ו‪ .CPD -‬ולכן‪ ,‬הזווית ‪ PCQ‬קטנה‬
‫מ‪ , -‬כלומר – קטנה מהזווית ‪.PBQ‬‬
‫את המקרה שהזווית ‪ PAQ‬גדולה יותר מ‪ PBQ-‬מראים באופן דומה‪.‬‬
‫∎‬
‫‪14‬‬
‫טענה‬
‫תהי  צלע של טריאנגולציה‪ ,‬כך ש‪  =  -‬שייכת לשני המשולשים‬
‫‪ ABC‬ו‪.ACD -‬‬
‫אזי  היא צלע חוקית אם ‪ D‬היא מחוץ למעגל החוסם את ‪ ABC‬והיא‬
‫צלע לא חוקית אם ‪ D‬היא בתוך המעגל החוסם‪.‬‬
‫‪15‬‬
‫הערה‪ :‬נשים לב שהמקרה האמצעי לא רלוונטי‪ ,‬כי הנחנו שאין ‪ 4‬נקודות על אותו מעגל‬
‫הוכחת הטענה‬
‫נסתכל על המקרה שבו ‪ D‬נמצאת בתוך המעגל החוסם את ‪ABC‬‬
‫(איור שמאלי)‪ .‬נראה שהצלע ‪ AC‬היא לא חוקית‪.‬‬
‫נסמן את ‪ 8‬הזוויות של המרובע ‪ ABCD‬הנוצרות מחיתוכי האלכסונים‪,‬‬
‫כפי שמתואר באיור הימני‪.‬‬
‫מכיוון ש‪ C-‬נמצאת מחוץ למעגל החוסם את ‪ ,ABD‬מהמשפט הקודם נובע‬
‫כי הזווית ‪ 1‬גדולה יותר מ‪ .1 -‬באותו אופן‪ ,‬מכיוון ש‪ A-‬נמצאת מחוץ‬
‫למעגל החוסם את ‪ ,BCD‬אזי הזווית ‪ 2‬גדולה יותר מ‪ .2 -‬אם נמשיך‬
‫באותו אופן‪ ,‬נקבל כי  >  לכל ‪.‬‬
‫‪16‬‬
‫הוכחת הטענה ‪ -‬המשך‬
‫כעת‪ ,‬מכיוון ש‪ D-‬נמצאת בתוך מעגל החוסם את ‪ ,ABC‬אזי הזוויות‬
‫‪ 1 , … ,4‬הן הזוויות הקטנות ביותר בסדרת הזוויות הנוצרות‬
‫ע"י הצלע ‪.AC‬‬
‫ולכן‪ ,‬עבור כל אחת מ‪ 4-‬הזוויות הנוצרות ע"י הצלע ‪ ,BD‬קיימת זווית קטנה‬
‫יותר הנוצרת ע"י הצלע ‪ .AC‬כלומר – ‪ AC‬היא צלע לא חוקית‪.‬‬
‫באופן דומה מוכיחים את המקרה שבו ‪ D‬נמצאת מחוץ למעגל החוסם‪.‬‬
‫∎‬
‫‪17‬‬
‫תרגיל‪:‬‬
‫בהינתן המשולשים מהטענה הקודמת‪ ,‬הראה ש‪ D -‬נמצאת מחוץ למעגל החוסם‬
‫את ‪ ABC‬אם"ם ‪ B‬נמצאת מחוץ למעגל החוסם את ‪.ACD‬‬
‫הוכח שזה נכון גם אם ‪ ABCD‬הוא לא מרובע קמור‪.‬‬
‫פתרון‪:‬‬
‫נניח כי ‪ D‬נמצאת מחוץ למעגל החוסם את המשולש ‪ ABC‬ונראה כי ‪ B‬נמצאת‬
‫מחוץ למעגל החוסם את ‪:ACD‬‬
‫המרובע ‪ AECB‬הוא מרובע חסום במעגל ועל כן ‪ . +  = 180°‬כעת‪ ,‬מכיוון‬
‫ש‪ D-‬נמצאת מחוץ למעגל חוסם של ‪ ,ABC‬ומכיוון שהיא נמצאת על אותה‬
‫הקשת כמו הזווית ‪ AEC‬הרי מתקיים ש‪ .  <  -‬מכאן נובע ש‪. +  -‬‬
‫‪< 180°‬‬
‫‪18‬‬
‫פתרון ‪ -‬המשך‪:‬‬
‫כעת‪ ,‬גם ‪ AFCD‬הוא מרובע חסום במעגל ולכן ‪.β +  = 180°‬‬
‫משתי המשוואות האחרונות נקבל כי  < ‪ .‬ומכיוון שהזוויות ‪ ABC‬ו‪AFC-‬‬
‫נשענות על אותה קשת ו‪ F-‬נמצאת על היקף המעגל החוסם של ‪,ACD‬‬
‫הרי ‪ B‬נמצאת מחוץ למעגל ‪.ACD‬‬
‫(הכיוון השני מוכח באותו אופן)‪.‬‬
‫נשים לב שהמרובע ‪ ABCD‬הוא לא קמור‪.‬‬
‫∎‬
‫‪19‬‬
‫משפט – תכונת המעגל הריק‪:‬‬
‫יהי ‪ S‬אוסף נקודות במצב כללי (כלומר – אין ‪ 4‬נקודות על אותו מעגל)‪.‬‬
‫אזי ‪ T‬היא טריאנגולציית ‪ Delaunay‬אם"ם שום נקודה של ‪ S‬לא נמצאת‬
‫בַ פְ נים של שום מעגל החוסם משולש של ‪.T‬‬
‫הוכחה ‪ -‬כיוון ראשון )⇒(‪:‬‬
‫אם אף נקודה של ‪ S‬היא לא פנימית לשום מעגל חוסם‪ ,‬אזי (לפי טענה‬
‫קודמת) כל היפוך יצור צלע לא חוקית‪ .‬מכאן – כל צלעות הטריאנגולציה‬
‫הן חוקיות‪.‬‬
‫‪20‬‬
‫הוכחה ‪ -‬כיוון שני )⇐(‪:‬‬
‫בשלילה‬
‫נניח כי ‪ T‬היא טריאנגולציית ‪ Delaunay‬ונניח כי קיימים משולשים כך‬
‫שהמעגלים החוסמים אותם מכילים נקודות בַ פְ נים שלהם‪ .‬מצב כזה מתואר‬
‫באיור ‪ a‬עבור משולש ‪ ABC‬ונקודה ‪ D‬בתוך המעגל החוסם אותו‪.‬‬
‫מכל המשולשים של ‪ T‬שהמעגל החוסם שלהם מכיל נקודות‪ ,‬נבחר בזה שבו‬
‫הנקודה ‪ D‬הכי קרובה לצלע של המשולש‪ .‬כלומר‪ ,‬נבחר במשולש שמביא‬
‫למינימום את המרחק ‪ x‬שמתואר באיור ‪.b‬‬
‫‪21‬‬
‫הוכחה ‪ -‬כיוון שני )⇐( ‪ -‬המשך‪:‬‬
‫כעת‪ ,‬מכיוון ש‪ T -‬היא טריאנגולציית ‪ Delaunay‬אזי כל הצלעות הן חוקיות‪.‬‬
‫לכן‪ ,‬מטענה קודמת‪ ,‬משולש ‪ BCD‬לא יכול להתקיים ב‪.T-‬‬
‫יהי ‪ BCE‬משולש סמוך למשולש ‪ ABC‬לאורך הצלע ‪ .BC‬לפי אותה טענה‪,‬‬
‫‪ E‬חייבת להיות מחוץ למעגל החוסם את ‪ ,ABC‬כפי שמתואר באיור ‪.c‬‬
‫נשים לב כי המעגל החוסם את ‪ BCE‬מכיל את הנקודה ‪ D‬וש‪ D-‬לא יכולה להיות‬
‫בתוך המשולש ‪( BCE‬מיד נראה למה זה מתקיים)‪.‬‬
‫מכאן – קיבלנו סתירה‪ D :‬היא נקודה בתוך המעגל החוסם את ‪ ,BCE‬שמרחקה‬
‫מהצלע ‪ EC‬קטן יותר מ‪.x-‬‬
‫∎‬
‫‪22‬‬
‫תרגיל‪:‬‬
‫הוכח כי המעגל החוסם את ‪ BCE‬מכיל את הנקודה ‪ D‬וש‪ D-‬לא יכולה להיות‬
‫בתוך המשולש ‪.BCE‬‬
‫הוכחה‪:‬‬
‫‪23‬‬
‫ראשית‪ ,‬נשים לב כי מכיוון שהמשולש ‪ BCE‬הוא חלק מטריאנגולציה‪ ,‬אזי הוא לא‬
‫מכיל שום נקודה בתוכו‪ .‬בפרט‪ D ,‬לא מוכלת בו‪.‬‬
‫כעת‪ ,‬נסתכל על המעגל החוסם את ‪ :ABC‬הזוויות ‪ BDC‬ו‪ BEC-‬נשענות על אותה‬
‫הקשת כאשר הנקודה ‪ D‬נמצאת בתוך המעגל והנקודה ‪ – E‬מחוצה לו‪.‬‬
‫אזי ממשפט קודם‪ ,‬הזווית ‪ BDC‬גדולה יותר מ‪.)*( – BEC -‬‬
‫כעת‪ ,‬אם נסתכל על הזוויות הללו ביחס למעגל החוסם את‬
‫המשולש ‪ ,BEC‬הזוויות הללו שוב נשענות על אותה קשת‪,‬‬
‫אך מכיוון ש‪ E-‬נמצאת על היקף המעגל ‪,BEC‬‬
‫ובצירוף (*)‪ ,‬נקבל כי ‪ D‬נמצאת בתוך המעגל‪.‬‬
‫∎‬
‫טריאנגולציות מיוחדות‪:‬‬
‫‪ ‬טריאנגולציה ממשקל מינימלי – ‪MWT‬‬
‫‪ ‬טריאנגולציות תואמות‬
‫‪ ‬פסאודו‪-‬טריאנגולציות‬
‫‪24‬‬
‫טריאנגולציה ממשקל מינימלי (‪)MWT‬‬
‫• מוגדרת להיות הטריאנגולציה שמשתמשת בהכי פחות דיו‬
‫ביחס לשאר הטריאנגולציות‪.‬‬
‫• לכל צלע יש משקל שמסמל את אורך הצלע‬
‫כיצד נוכל למצוא טריאנגולציה כזו?‬
‫‪25‬‬
‫דוגמא‪:‬‬
‫יהי אוסף של ‪ 33‬נקודות‪ ,‬כך ש‪ 32-‬מהן מונחות במרווחים שווים על מעגל ברדיוס‬
‫‪ 1‬והנקודה האחרונה במרכז המעגל‪ .‬נזיז טיפה את הנקודות כך שלא יהיו ‪4‬‬
‫נקודות על אותו מעגל‪.‬‬
‫• עבור טריאנגולציה אחת ניקח כל אחת מנקודות שפת הקמור ונחבר‬
‫עם מרכז המעגל‪.‬‬
‫• עבור טריאנגולציה שנייה נחבר את כל הנקודות הסמוכות של שפת הקמור‪.‬‬
‫כעת נחבר כל נקודה שנייה‪ ,‬ובכך ניצור ‪ 16‬צלעות חדשות‪ ,‬אח"כ נוסיף עוד ‪8‬‬
‫צלעות חדשות ע"י חיבור כל נקודה רביעית של השפה‪ .‬לאחר חיבור כל נקודה‬
‫שמינית של השפה נסיים את הטריאנגולציה ע"י הוספת צלע מכל נקודה‬
‫שמינית אל מרכז המעגל‪.‬‬
‫‪26‬‬
‫דוגמא ‪ -‬המשך‪:‬‬
‫נשים לב שהטריאנגולציה הראשונה היא טריאנגולציית ‪( Delaunay‬למה?)‬
‫כעת נראה שמשקלה הכולל של הטריאנגולציה השנייה קטן יותר מזו של‬
‫טריאנגולציית ‪.Delaunay‬‬
‫המשקל הכולל של טריאנגולציית ‪ Delaunay‬קרוב ל‪: 2 + 32 -‬‬
‫היקף המעגל ‪ 32 +‬הרדיוסים‪.‬‬
‫המשקל הכולל של הטריאנגולציה השנייה הוא הרבה פחות מ‪ , 8 + 4 -‬כאשר‬
‫‪ 8‬מייצג את ארבע השכבות מסביב למעגל ו‪ 4-‬הוא אורכן של ארבעת הצלעות‬
‫שמחוברות למרכז המעגל‪.‬‬
‫כעת‪ ,‬מכיוון ש‪ 2π + 32 ≈ 38 > 29 ≈ 8 + 4 -‬קיבלנו דוגמה למצב שבו‬
‫טריאנגולציית ‪ Delaunay‬היא לא טריאנגולציה ממשקל מינימלי (‪.)MWT‬‬
‫‪27‬‬
‫תרגיל‪:‬‬
‫הראה שהטריאנגולציה הראשונה היא טריאנגולציית ‪.Delaunay‬‬
‫הוכחה‪:‬‬
‫‪28‬‬
‫אלגוריתם חמדן למציאת ‪:MWT‬‬
‫‬
‫• בהינתן ‪ n‬נקודות‪ ,‬ישנם‬
‫‪2‬‬
‫• נוסיף כל פעם צלע אחת לטריאנגולציה הגדלה‪ ,‬כשבכל צעד נבחר בצלע‬
‫מאורך מינימלי שלא חוצה את הצלעות שנוספו מקודם‪.‬‬
‫מרחקים שונים ביניהן‪.‬‬
‫‪ Errol Lloyd ‬הוכיח שאלגוריתם זה לא יוצר טריאנגולציית ‪ MWT‬ואף‬
‫לא טריאנגולציית ‪ .Delaunay‬יתרה מזאת‪ ,‬במשך הרבה זמן חישוב‬
‫הסיבוכיות של מציאת טריאנגולציית ‪ MWT‬הייתה בעיה פתוחה‪.‬‬
‫הבעיה נפתרה ב‪ 2006-‬ע"י ‪ Wolfgang Mulzer‬ו‪ Gunter Rote -‬שהראו‬
‫שהבעיה היא ‪( NP-hard‬שזה לפחות כמו ‪.)NP-complete‬‬
‫‪29‬‬
‫דוגמא‪:‬‬
‫‪30‬‬
‫אורך ההיקף הוא ‪ 100‬יחידות‬
‫מה אם במקום טריאנגולציה מלאה של קבוצת נקודות‪ ,‬היינו‬
‫מעוניינים רק בעץ שפורש את קבוצת הנקודות?‬
‫במילים אחרות‪ ,‬נרצה לצייר צלעות תוך שימוש קטן ביותר בדיו‪ ,‬כך‬
‫שכל הנקודות מחוברות זו לזו‪ .‬כלומר ‪ -‬מדובר בעץ פורש מינימלי‬
‫‪31‬‬
‫משפט‪:‬‬
‫תהי ‪ S‬קבוצת נקודות‪ .‬אזי עץ פורש מינימלי של ‪ S‬הוא תת‪-‬קבוצה של‬
‫טריאנגולציית ‪.Delaunay‬‬
‫הוכחה ‪ -‬בשלילה‪:‬‬
‫נניח כי הצלע ‪ AB‬נמצאת בעץ פורש מינימלי של ‪ S‬אבל לא בטריאנגולציית‬
‫‪ .Delaunay‬נסתכל במעגל שצלע ‪ AB‬מהווה את הקוטר שלו‪ .‬מכיוון ש‪ AB-‬היא‬
‫צלע לא חוקית (מהגדרת טריאנגולציית ‪ ,)Delaunay‬אזי מטענה קודמת‪ ,‬חייבת‬
‫להיות נקודה נוספת במעגל‪ .‬נסמן אותה ב‪ .C -‬כעת‪ ,‬מכיוון ש‪ AB-‬הוא קוטר‬
‫המעגל‪ ,‬הרי מתקיים‪  <  :‬וגם  <  ‪.‬‬
‫‪32‬‬
‫הוכחה ‪ -‬המשך‪:‬‬
‫מחיקת ‪ AB‬מהעפ"מ תפצל את העץ לשני עצים‪ ,‬נניח  ו‪ . -‬מכיוון‬
‫שהעפ"מ פורש את כל נקודות ‪ ,S‬אזי ‪ C‬נמצאת באחד מ‪ 2-‬העצים‪,‬‬
‫נניח ב‪ . -‬כעת‪ ,‬הסרת ‪ AB‬מהעפ"מ והוספת ‪ BC‬תיצור עץ פורש‬
‫מינימלי חדש שאורכו הכולל קטן יותר‪ .‬בסתירה‪.‬‬
‫∎‬
‫‪33‬‬
‫בעיה פתוחה‪:‬‬
‫נניח כי משקלן הכללי של כל הצלעות בטריאנגולציית ‪ MWT‬נתון‪.‬‬
‫מצא את טריאנגולציית ‪ MWT‬בזמן פולינומיאלי‪.‬‬
‫‪34‬‬
‫טריאנגולציות תואמות‬
‫יש מקרים בהם נעדיף להשוות ‪ 2‬טריאנגולציות של ‪ 2‬קבוצות‬
‫שונות (אך קשורות) של נקודות ‪ X‬ו‪ Y-‬כשלכל אחת מהן יש ‪n‬‬
‫נקודות‪.‬‬
‫למשל‪ ,‬יצירת אנימציה תלת‪-‬ממדית של דמות ע"י צילום תנועות של‬
‫שחקן שעליו יש עשרות סמנים משתקפים (מרקרים מחזירי אור)‪.‬‬
‫המחשב מסתכל על תנועת כל הסמנים ונעזר בתנועותיהם כדי‬
‫להנפיש את הדמות‪.‬‬
‫במקרה הזה‪ X ,‬ו‪ Y-‬מייצגים ‪ 2‬תצלומים של הסמנים בזמנים שונים‬
‫והטריאנגולציות מהוות אינטרפולציה עבור נקודות הביניים‪.‬‬
‫‪35‬‬
‫הגדרה‪:‬‬
‫יהיו ‪ X,Y‬שני אוספי נקודות במישור‪ ,‬בעלי ‪ n‬נקודות כל אחד‪,‬‬
‫ותהיינה ‪  ,‬טריאנגולציות שלהם‪.‬‬
‫נאמר כי  ו‪  -‬טריאנגולציות תואמות אם קיימת פונקציה‬
‫חח"ע ועל  בין נקודות של ‪ X‬ו‪ Y-‬כך ש‪ ABC-‬הוא משולש של ‬
‫אם"ם )()()( הוא משולש של ‪.‬‬
‫דוגמא‪:‬‬
‫‪36‬‬
‫ניזכר במשפט מהרצאה קודמת‪ :‬מספר המשולשים של כל‬
‫טריאנגולציה עם ‪ n‬נקודות‪ ,‬כש‪ h-‬מהם בקמור הוא ‪.2 + ℎ − 2‬‬
‫לכן תנאי הכרחי לטריאנגולציות תואמות הוא שהקמור של שני אוספי‬
‫הנקודות יכיל אותו מס' של נקודות‪.‬‬
‫אך האם זהו תנאי מספיק?‬
‫זוהי בעיה פתוחה שנפתרה אך ורק עבור אוספי נקודות שבהם יש לכל‬
‫היותר ‪ 3‬נקודות פנימיות‪.‬‬
‫‪37‬‬
‫מציאת טריאנגולציות תואמות כרוכה במציאת פונקציה חח"ע ועל בין‬
‫הנקודות תוך כדי מציאת טריאנגולציה באופן סימולטני‪ .‬כשלא ניתן‬
‫לעשות את האחד לפני האחר‪.‬‬
‫‪ Alan Saalfeld‬הראה ב‪ 1987-‬שאם נקבע קודם את הפונקציה הנ"ל‪,‬‬
‫אזי לא תמיד קיימות טריאנגולציות תואמות‪.‬‬
‫‪38‬‬
‫תרגיל‪:‬‬
‫בהינתן שני מצולעים עם ‪ n‬קודקודים‪ ,‬האם תמיד אפשר לבצע‬
‫טריאנגולציה מתואמת של שני המצולעים?‬
‫תשובה‪:‬‬
‫לא‪ .‬דוגמא‪:‬‬
‫‪39‬‬
‫בעיית מציאת טריאנגולציות תואמות יכולה להיות קלה יותר אם‬
‫נרשה להוסיף נקודות נוספות לאוסף הנקודות‪ .‬נקודות אלה נקראות‬
‫נקודות ‪ Steiner‬על שם ‪ – Jacob Steiner‬מתמטיקאי שוויצרי שחי‬
‫במאה ה‪.19-‬‬
‫שיטה אחת במציאת טריאנגולציות תואמות היא להוסיף נקודות‬
‫‪ Steiner‬מחוץ לקמור של אוסף הנקודות המקורי‪ .‬נקרא לנקודות‬
‫כאלה נקודות ‪ Steiner‬חיצוניות‪.‬‬
‫‪40‬‬
‫משפט‪:‬‬
‫לכל שני אוספי נקודות ‪ S‬ו‪ ,T-‬בעלי ‪ n‬נקודות כל אחד‪ ,‬ניתן למצוא‬
‫טריאנגולציות תואמות ע"י הוספת ‪ 2‬נקודות ‪ Steiner‬חיצוניות ל‪ S-‬ול‪.T-‬‬
‫הוכחה‪:‬‬
‫נסדר כל אוסף נקודות בסדר עולה של ערכי ‪ y‬ובמקרה שיש נקודות בעלי‬
‫אותה קואורדינטת ‪ ,y‬נסדר אותן בסדר יורד של ערכי ‪.x‬‬
‫נקבל‪ = {1 = 1 ,1 , … , =  , } :‬‬
‫כאשר‪ ,‬אם  >  אזי  >  או  =  וגם  < ‪.‬‬
‫ובאותו אופן ‪T = {1 = 1 ,1 , … , =  , } -‬‬
‫כאשר אם  >  אזי  >  או  =  וגם  < ‪.‬‬
‫‪41‬‬
‫הערה‪ :‬אם נניח שאין ‪ 2‬נקודות עם אותה קואורדינטת ‪ ,y‬אזי ניתן‬
‫להסתפק במיון של ערכי ‪.y‬‬
‫הוכחה ‪ -‬המשך‪:‬‬
‫כעת‪ ,‬נוסיף ‪ 2‬נקודות ‪ Steiner‬חיצוניות‪:‬‬
‫ שתהיה קצת מתחת ל‪ 1 -‬ובמרחק מספיק גדול משמאל ל‪ ,S -‬כך‬
‫שהצלעות ‪(  +1‬בין ‪ 2‬נקודות עוקבות) והצלעות   (בין  ונקודות‬
‫של ‪ )S‬לא יחצו אחת את השנייה‪ .‬ובאופן דומה ‪ -  -‬שתהיה מעט מעל‬
‫ ובמרחק מספיק גדול מימין ל‪.S -‬‬
‫באותו אופן‪ ,‬נצרף את הנקודות  ו‪  -‬ל‪.T -‬‬
‫‪42‬‬
‫הוכחה ‪ -‬המשך‪:‬‬
‫נשים לב‪ ,‬שהנקודות  ו‪  -‬קיימות (ומאותה סיבה גם  ו‪,) -‬‬
‫מכיוון שהצבתן במרחק רב משאר הנקודות יוצרת צלעות כמעט אופקיות‬
‫(ואז זה בעצם כמו להעביר קווים מקבילים לציר ה‪.)X-‬‬
‫‪43‬‬
‫הוכחה ‪ -‬המשך‪:‬‬
‫כעת‪ ,‬יהיו ‪  ′ =  ∪  ,‬ו‪. ′ =  ∪  , -‬‬
‫לפי הבנייה‪ ,‬הצלעות   ו‪(   -‬המחברים בין נק' ‪ Steiner‬לכל‬
‫נקודה באוסף המקורי)‪ ,‬יחד עם הצלעות ‪  +1‬יוצרים טריאנגולציה של‬
‫‪ .  ′‬בנייה דומה יוצרת טריאנגולציה של ‪.  ′‬‬
‫הפונקציה ∗ = ∗  מראה ששתי הטריאנגולציות תואמות‪.‬‬
‫∎‬
‫‪44‬‬
‫משפט זה הראה את היתרון שבהוספת נקודות ‪ Steiner‬חיצוניות‪.‬‬
‫אך נקודות אלה יכולות להיות רחוקות מאוד‪ ,‬מה שיכול ליצור‬
‫בעיה‪.‬‬
‫פתרון טוב יותר יכול להיות כאשר מוסיפים נקודות ‪Steiner‬‬
‫ל ְַפנים של הקמור‪ .‬אך בעיה זו הרבה יותר מסובכת והתוצאות הכי‬
‫טובות עד כה היו בהוספת ‪ n-h-3‬נקודות ‪ Steiner‬פנימיות‪.‬‬
‫‪45‬‬
‫פסאודו‪-‬טריאנגולציות‬
‫הגדרה‪:‬‬
‫פסאודו‪-‬משולש זהו מצולע עם בדיוק ‪ 3‬קודקודים קמורים‪.‬‬
‫במקום ‪ 3‬צדדים ישרים המחברים בין שלושת הקודקודים‪,‬‬
‫לפסאודו‪-‬משולשים יש שרשראות (אולי ריקות) של קודקודים‬
‫קעורים שמחברות בין ‪ 3‬קודקודים קמורים‪ .‬בפרט‪ ,‬כל משולש הוא‬
‫פסאודו‪-‬משולש‪.‬‬
‫‪46‬‬
‫תרגיל‪:‬‬
‫הראה שלכל מצולע חייבים להיות לפחות ‪ 3‬קודקודים קמורים‪.‬‬
‫פתרון ‪ -‬אינטואיטיבי‪:‬‬
‫אפשר להגיד שמספר הקודקודים הקמורים של מצולע הוא כמספר‬
‫הקודקודים שנמצאים בקמור של המצולע‪.‬‬
‫לכן‪ ,‬מכיוון שהקמור המינימלי של מצולע הוא משולש‪ ,‬אזי לכל‬
‫מצולע יש לפחות ‪ 3‬קודקודים קמורים‪.‬‬
‫‪47‬‬
‫תרגיל‪:‬‬
‫הראה שהקמור של כל פסאודו‪-‬משולש הוא משולש‪.‬‬
‫פתרון‪:‬‬
‫לפי האינטואיציה מקודם – שמס' הקודקודים הקמורים של מצולע‬
‫הוא כמס' הקודקודים שנמצאים בקמור של המצולע‪.‬‬
‫ומכיוון שלפסאודו‪-‬משולש יש בדיוק ‪ 3‬קודקודים קמורים‪ ,‬אזי‬
‫לקמור שלו יש ‪ 3‬קודקודים‪ ,‬כלומר – הקמור שלו מהווה משולש‪.‬‬
‫בפועל – נחבר בין שלושת הקודקודים הקמורים של הפסאודו‪-‬‬
‫משולש ובכך ניצור משולש‪.‬‬
‫‪48‬‬
‫הגדרה‪:‬‬
‫נאמר שקודקוד הוא משונן אם אחת מזוויות שהוא מגדיר‬
‫גדולה מ‪.180° -‬‬
‫נאמר שפסאודו‪-‬טריאנגולציה היא משוננת אם כל הקודקודים שלה‬
‫משוננים‪.‬‬
‫‪49‬‬
‫נזכר במשפט האומר שבהינתן אוסף עם ‪ h‬נקודות בקמור ו‪ k-‬בפנים‪,‬‬
‫אזי בכל טריאנגולציה יש בדיוק ‪ 2k+h-2‬משולשים‪.‬‬
‫נשים לב‪ ,‬שמשפט זה לא תקף במקרה של פסאודו‪-‬טריאנגולציה‪.‬‬
‫משפט‪:‬‬
‫לפסאודו‪-‬טריאנגולציה של אוסף נקודות ‪ S‬עם ‪ p‬קודקודים משוננים‬
‫ו‪ q-‬לא משוננים‪ ,‬יש ‪ p+2q-2‬פסאודו‪-‬משולשים ו‪ 2p+3q-3 -‬צלעות‪.‬‬
‫‪50‬‬
‫הוכחת המשפט‪:‬‬
‫יהי ‪ t‬מס' הפסאודו‪-‬משולשים ו‪ e-‬מס' צלעות הפסאודו‪-‬טריאנגולציה‪.‬‬
‫מנוסחת אוילר (‪ ) −  +  = 2‬נקבל‪:‬‬
‫‪ ,  +  −  +  + 1 = 2‬מכיוון שיש ‪ t‬פאות חסומות ועוד אחת‬
‫לא חסומה‪.‬‬
‫כעת‪ ,‬מכיוון שכל זווית סמוכה לקודקוד הנוצר ע"י ‪ 2‬צלעות‪ ,‬אזי המס'‬
‫הכולל של הזוויות הוא ‪ .2e‬מס' הזוויות הקעורות הוא ‪ ,p‬אחת בכל‬
‫קודקוד משונן‪ ,‬ומס' הזוויות הקמורות שווה ל‪ ,3t-‬אחת לכל קודקוד‬
‫של פסאודו‪-‬משולש‪ .‬לכן נקבל ‪.2 =  + 3‬‬
‫בעזרת ‪ 2‬הנוסחאות הללו‪ ,‬נחלץ את ‪ e‬ו‪ t-‬ונקבל את הדרוש‪.‬‬
‫∎‬
‫מסקנה‪:‬‬
‫‪51‬‬
‫לפסאודו‪-‬טריאנגולציה משוננת של אוסף נקודות ‪ S‬עם ‪ n‬נקודות‪ ,‬יש‬
‫‪ n-2‬פסאודו‪-‬משולשים ו‪ 2n-3 -‬צלעות‪.‬‬
‫משפט‪:‬‬
‫לפסאודו‪-‬טריאנגולציה משוננת ‪ T‬יש בדיוק היפוך אחד לכל צלע‬
‫פנימית ‪ e‬של ‪ ,T‬עבורה קיימת צלע יחידה ’‪ e‬כך שהסרת ‪ e‬מ‪T-‬‬
‫והחלפתה ב‪ e’-‬יוצרת שוב פסאודו‪-‬טריאנגולציה משוננת‪.‬‬
‫‪52‬‬
‫תרגיל‪:‬‬
‫הראה שמחיקת צלע שמשותפת לשני פסאודו‪-‬משולשים בפסאודו‪-‬‬
‫טריאנגולציה משוננת יוצרת פסאודו‪-‬מרובע‪ ,‬כלומר מצולע (ייתכן כי‬
‫מנוון) בעל בדיוק ‪ 4‬קודקודים קמורים‪.‬‬
‫פתרון‪:‬‬
‫‪53‬‬
‫נסתכל על הפסאודו‪-‬משולשים ‪ ABEC‬ו‪ACDF-‬‬
‫(שצלע ‪ AC‬משותפת לשניהם) של פסאודו‪-‬‬
‫טריאנגולציה משוננת נתונה‪.‬‬
‫אם נוריד את הצלע ‪ ,AC‬נקבל פסאודו‪-‬מרובע‬
‫‪ .ABECDF‬כעת‪ ,‬מכיוון שהראנו שקמור של‬
‫פסאודו‪-‬משולש הוא משולש‪ ,‬אזי מכיוון שקמור‬
‫של מרובע הנוצר מ‪ 2-‬משולשים בעלי צלע משותפת‬
‫הוא מרובע‪ ,‬הקמור של פסאודו‪-‬מרובע הנוצר ע"י ‪2‬‬
‫פסאודו‪-‬משולשים בעלי צלע משותפת הוא מרובע‪,‬‬
‫ולכן מכיל ‪ 4‬קודקודים קמורים בשפה שלו‪.‬‬
‫∎‬
‫סוף‬
‫תודה על ההקשבה!‬
‫‪54‬‬

similar documents