הצגת המקור של הדף "שילוש דלוני"

[[קובץ:Delaunay Triangulation (100 Points).svg|ממוזער|שמאל|250px|דוגמה לשילוש דלוני של 100 נקודות שרירותיות במישור]]
ב[[גאומטריה חישובית]], '''שילוש דלוני''' או "תילות דלוני" של קבוצת נקודות ב[[מישור (גאומטריה)|מישור]] הוא [[שילוש (גאומטריה)|שילוש]] של קבוצת הנקודות (כלומר, חלוקה של ה[[קמור]] של קבוצת הנקודות למשולשים כך שכל הנקודות בקבוצה הן קודקודים של ה[[משולש]]ים) כך שאף נקודה אינה נמצאת בתוך ה[[מעגל]] החוסם אחד מהמשולשים. תכונה זו של השילוש הופכת אותו לאופטימלי, מבחינות מסוימות, משום שהיא מבטיחה שהמשולשים שירכיבו את השילוש יהיו עבים ושמנים, ולא ארוכים ודקים.

==הגדרה פורמלית==
ישנן מספר דרכים שקולות להגדיר שילוש דלוני עבור קבוצת נקודות במישור:
*זהו שילוש בו עבור כל משולש, המעגל החוסם אותו אינו מכיל אף נקודה מקבוצת הנקודות.
* זהו שילוש שלכל צלע שלו יש מעגל העובר דרך קצות הצלע ואינו מכיל אף נקודה אחרת.
*זהו שילוש שהוא מקסימלי ביחס לשילושים האחרים מבחינת גודל הזווית הקטנה ביותר שבו. כלומר, כל המשולשים שבו קרובים ככל הניתן להיות [[משולש שווה-צלעות|שווי צלעות]]. מבחינה פורמלית, אם נתאים לכל שילוש [[וקטור (אלגברה)|וקטור]] <math>\ \left(\alpha_1,\alpha_2,\dots,\alpha_n\right)</math> בו מסודרת לפי סדר עולה הזוויות של המשולשים בשילוש, שילוש דלוני יהיה זה שהוא מקסימלי על פי [[יחס סדר|יחס הסדר]] [[סדר לקסיקוגרפי|הלקסיקוגרפי]] הנקבע על הווקטורים.
*זהו שילוש המתקבל מ[[דיאגרמת וורונוי]] של קבוצת הנקודות על ידי חיבור בקו של כל שתי נקודות שתאי וורונוי שלהן סמוכים.

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

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

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* [http://web.mit.edu/alexmv/Public/6.850-lectures/lecture09.pdf מצגת של הרצאה] על שילוש דלוני מ-[[MIT]]
* {{MathWorld}}

{{בקרת זהויות}}

[[קטגוריה:גאומטריה חישובית]]
[[קטגוריה:משולש]]