Тріангуляція Делоне

Тріангуляція Делоне дискретної множини точок P в загальному випадку відповідає дуальному графу розбиття Вороного для P. Особливі випадки включають існування трьох точок на одній прямій, та чотирьох точок на колі.

Тріангуляція Делоне зі всіма колами та їх центрами (червоні).

З'єднання центрів описаних кіл трикутників які мають спільне ребро утворює діаграму Вороного (червона).

Для множини P точок d-вимірного Евклідового простору, тріангуляція Делоне це тріангуляція DT(P) така що жодна з точок з P не лежить всередині гіперсфери описаної навколо будь-якого симплексу з DT(P). Відомо що[2] існує єдина тріангуляція Делоне для P, якщо P множина точок в загальній позиції; така що не існує підпростору розмірності k що містить ${\displaystyle k+2}$ точок ні k-сфери що містить ${\displaystyle k+3}$ точок, для ${\displaystyle 1\leq k\leq d-1}$ (тобто, наприклад для множини точок в ${\displaystyle \mathbb {R} ^{3}}$ не існує трьох точок що лежать на одній прямій, не існує чотирьох що лежать в одній площині, і жодні п'ять точок не лежать на одній сфері).

Задача знаходження тріангуляції Делоне для множини точок в d-вимірному просторі може бути зведена до задачі знаходження опуклої оболонки множини точок в ${\displaystyle (d+1)}$-вимірному просторі, додаючи кожній точці p додаткову координату яка дорівнює ${\displaystyle |p|^{2}}$, беручи нижню частину опуклої оболонки, і відображаючи її назад в d-вимірний простір видаленням останньої координати. Так як опукла оболонка єдина, то тріангуляція теж, вважаючи, що всі сегменти опуклої оболонки — симплекси. Не симплексні сегменти з'являються лише коли ${\displaystyle d+2}$ різних точок лежить на одній d-гіперсфері, тобто точки не знаходяться в загальній позиції.

Нехай n — кількість точок, а d — розмірність.

• Об'єднання всіх симплексів в тріангуляції — опукла оболонка точок.
• Тріангуляція Делоне містить щонайбільше O(n^{⌈d / 2⌉}) симплексів.[3]
• Якщо на площині (d = 2), b вершин входять до опуклої оболонки, то будь-яка тріангуляція точок має щонайбільше ${\displaystyle 2n-2-b}$ трикутників, і ще одну зовнішню «грань» (див. характеристика Ейлера).
• На площині, кожна вершина має в середньому шість інцидентних трикутників.
• На площині, тріангуляція Делоне максимізує найменший кут. Найменший кут в тріангуляції Делоне, буде не меншим ніж в будь-якій іншій тріангуляції. Правда тріангуляція Делоне не обов'язково мінімізує максимальний кут.
• Коло описане навколо довільного трикутника тріангуляції не містить всередині жодних інших вхідних вершин.
• Якщо коло що проходить через дві вхідні точки не містить всередині жодних інших, тоді сегмент що з'єднує ці дві точки є ребром тріангуляції Делоне цих точок.
• Тріангуляція Делоне множини точок в d-вимірному просторі є проекцією точок опуклої оболонки на (${\displaystyle d+1}$)-мірний параболоїд.
• Найближчий сусід b довільної точки p лежить на ребрі bp тріангуляції Делоне, бо граф найближчих сусідів — підграф тріангуляції Делоне.

Якщо розглядати два трикутники ABD та BCD зі спільним ребром BD (див. малюнки), якщо ${\displaystyle \alpha +\gamma \leq 180^{\circ }}$, трикутники задовольняють умові Делоне.

Це важлива властивість, бо дозволяє використовувати техніку заміни ребра. Якщо два трикутники не задовольняють умові Делоне, заміна спільного ребра BD на ребро AC утворює два інші трикутники які задовольняють умові Делоне:

• 
  Тріангуляція не відповідає умові Делоне бо ${\displaystyle \alpha +\gamma >180^{\circ }}$.
• 
  І описані навколо трикутників кола містять більше трьох точок.
• 
  Заміна спільного ребра створює для чотирьох точок тріангуляцію що відповідає умові Делоне.

Зауважте, що найменший кут тріангуляції збільшився.

Багато алгоритмів для обчислення тріангуляції Делоне спираються на швидкі операції для визначення того, чи точка знаходиться всередині описаного навколо трикутника кола, і ефективних структур даних для зберігання трикутників та ребер. В двовимірному випадку, якщо D знаходиться всередині кола описаного навколо A, B, C треба перевірити чи визначник:[4]

${\displaystyle {\begin{vmatrix}A_{x}&A_{y},&A_{x}^{2}+A_{y}^{2},&1\\[6pt]B_{x}&B_{y},&B_{x}^{2}+B_{y}^{2},&1\\[6pt]C_{x}&C_{y},&C_{x}^{2}+C_{y}^{2},&1\\[6pt]D_{x}&D_{y},&D_{x}^{2}+D_{y}^{2},&1\end{vmatrix}}={\begin{vmatrix}A_{x}-D_{x},&A_{y}-D_{y},&(A_{x}^{2}-D_{x}^{2})+(A_{y}^{2}-D_{y}^{2})\\[6pt]B_{x}-D_{x},&B_{y}-D_{y},&(B_{x}^{2}-D_{x}^{2})+(B_{y}^{2}-D_{y}^{2})\\[6pt]C_{x}-D_{x},&C_{y}-D_{y},&(C_{x}^{2}-D_{x}^{2})+(C_{y}^{2}-D_{y}^{2})\\[6pt]\end{vmatrix}}>0}$

Коли A, B та C впорядковані проти годинникової стрілки визначник додатній тоді і тільки тоді, коли D знаходиться всередині описаного кола.

Евклідове мінімальне кістякове дерево множини точок є підмножиною тріангуляції Делоне тих самих точок, і це можна використати щоб обчислювати це дерево ефективніше.

Для моделювання місцевості, чи інших об'єктів що задані множиною вибраних точок, тріангуляція Делоне дає гарний набір трикутників для використання як полігони моделі. Зокрема, тріангуляція Делоне уникає вузьких трикутників (з маленькими кутами, бо вони мають великі описані кола, порівняно з власною площею). Дивіться статтю тріангульована нерегулярна мережа (triangulated irregular network).

Тріангуляція Делоне для випадкового набору 100 точок площини.

Тріангуляції Делоне часто використовуються для побудови мешів для методу скінченних елементів, через гарні кути, та швидкі алгоритми побудови. Зазвичай, об'єкт для якого потрібно побудувати меш, грубо задається як симпліціальний комплекс; щоб він був чисельно стабільним він має бути уточненим, наприклад за допомого алгоритму Руперта (Ruppert's algorithm). Це було реалізовано Джонатаном Шевчуком, і вільно доступно в пакеті Triangle.

• Тріангуляція Делоне в Computational Geometry Algorithms Library:
  • Yvinec, Mariette. 2D Triangulation. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011.
  • Pion, Sylvain; Teillaud, Monique. 3D Triangulations. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011.
  • Hert, Susan; Seel, Michael. dD Convex Hulls and Delaunay Triangulations. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011.
• Delaunay triangulation. Wolfram MathWorld.
• Qhull. Архів оригіналу за 26 червня 2013. Процитовано 9 травня 2019. — Код для побудови опуклої оболонки, тріангуляції Делоне, діаграми Вороного та перетину півпросторів
• Shewchuk, Jonathan Richard. Triangle. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011. — Генератор двовимірного мешу, та тріангулятор Делоне
• Kumar, Piyush; Mohanty, Somya. Triangle++. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011. — Triangle пристосований до C++
• Poly2Tri. Google Code. Архів оригіналу за 26 червня 2013. Процитовано 14 квітня 2011. — Бібліотека тріангуляцій Делоне методом замітання, доступна на ActionScript 3, C++, C#, Java, Javascript, Python та Ruby.