שילוש דלוני

דוגמה לשילוש דלוני של 100 נקודות שרירותיות במישור

בגאומטריה חישובית, שילוש דלוני או "תילות דלוני" של קבוצת נקודות במישור הוא שילוש של קבוצת הנקודות (כלומר, חלוקה של הקמור של קבוצת הנקודות למשולשים כך שכל הנקודות בקבוצה הן קודקודים של המשולשים) כך שאף נקודה אינה נמצאת בתוך המעגל החוסם אחד מהמשולשים. תכונה זו של השילוש הופכת אותו לאופטימלי, מבחינות מסוימות, משום שהיא מבטיחה שהמשולשים שירכיבו את השילוש יהיו עבים ושמנים, ולא ארוכים ודקים.

הגדרה פורמלית

ישנן מספר דרכים שקולות להגדיר שילוש דלוני עבור קבוצת נקודות במישור:

• זהו שילוש בו עבור כל משולש, המעגל החוסם אותו אינו מכיל אף נקודה מקבוצת הנקודות.
• זהו שילוש שלכל צלע שלו יש מעגל העובר דרך קצות הצלע ואינו מכיל אף נקודה אחרת.
• זהו שילוש שהוא מקסימלי ביחס לשילושים האחרים מבחינת גודל הזווית הקטנה ביותר שבו. כלומר, כל המשולשים שבו קרובים ככל הניתן להיות שווי צלעות. מבחינה פורמלית, אם נתאים לכל שילוש וקטור $\ \left(\alpha _{1},\alpha _{2},\dots ,\alpha _{n}\right)$ בו מסודרת לפי סדר עולה הזוויות של המשולשים בשילוש, שילוש דלוני יהיה זה שהוא מקסימלי על פי יחס הסדר הלקסיקוגרפי הנקבע על הווקטורים.
• זהו שילוש המתקבל מדיאגרמת וורונוי של קבוצת הנקודות על ידי חיבור בקו של כל שתי נקודות שתאי וורונוי שלהן סמוכים.

ההגדרה האחרונה מספקת שיטה למציאת שילוש דלוני של קבוצת נקודות בזמן $\ O(n\log n)$ על ידי מציאת דיאגרמת וורונוי של קבוצת הנקודות.

אם הנקודות נמצאות "במצב כללי" (כלומר, אין שלוש נקודות על אותו ישר, ואין ארבע נקודות על אותו מעגל), אז קיים שילוש דלוני יחיד. לעומת זאת, אם יש בקבוצה שלוש נקודות על אותו קו, לא קיים שילוש שאינו מנוון, ואם יש ארבע נקודות על אותו מעגל, השילוש אינו יחיד.

קישורים חיצוניים

מדיה וקבצים בנושא שילוש דלוני בוויקישיתוף

• מצגת של הרצאה על שילוש דלוני מ-MIT
• שילוש דלוני, באתר MathWorld (באנגלית)