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