Тріангуляція множини точок

Тріангуляція множини точок ${\mathcal {P}}$ в евклідовому просторі $\mathbb {R} ^{d}$ — це симпліційний комплекс, що охоплює опуклу оболонку ${\mathcal {P}}$, і вершини якого належать ${\mathcal {P}}$. У площині (коли ${\mathcal {P}}$ — це множина точок з $\mathbb {R} ^{2}$), триангуляція складається з трикутників разом із їхніми ребрами та вершинами. Деякі автори вимагають, щоб усі точки ${\mathcal {P}}$ були вершинами його тріангуляції. У цьому випадку тріангуляція множини точок ${\mathcal {P}}$ в площині можна також визначити як максимальний набір ребер, які не перетинаються та з'єднують точки ${\mathcal {P}}$. У площині, тріангуляція — це особливі випадки плоских прямолінійних графів.

Двв різні трикутники одного і того ж набору з 9 точок у площині.

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

Тріангуляція має численні застосування, та існує сенс у побудові «гарних» тріангуляцій множини точок за певними критеріями, наприклад, тріангуляція мінімальної ваги. Іноді бажано мати тріангуляції зі спеціальними властивостями, наприклад, коли всі трикутники мають великі кути, що, в свою чергу, дозволяє уникнути довгих та вузьких «осколкових» трикутників.

Для заданої множини ребер, що з'єднують точки площини, задача визначення того, чи містять вони триангуляцію, є NP-повною.

Регулярні триангуляції

Деякі тріангуляції множини точок ${\mathcal {P}}\subset \mathbb {R} ^{d}$ можна отримати, якщо «підняти» точки ${\mathcal {P}}$ у простір $\mathbb {R} ^{d+1}$ (що означає додати координату $x_{d+1}$ для кожної точки ${\mathcal {P}}$), обчислити опуклу оболонку піднятої множини точок, і зробити проєкцію нижніх граней опуклої оболонки на $\mathbb {R} ^{d}$. Побудовані таким чином тріангуляції називають регулярними тріангуляціями ${\mathcal {P}}$. Якщо ж точки підняти на параболоїд, заданий рівнянням $x_{d+1}=x_{1}^{2}+\cdots +x_{d}^{2}$, ця конструкція стає тріангуляцією Делоне ${\mathcal {P}}$. Зауважте, що для того, щоб ця конструкція забезпечувала тріангуляцію, нижня опукла оболонка піднятої множини точок повинна бути симпліційною. Для тріангуляції Делоне це накладає вимогу, щоб ніякі $d+2$ точки ${\mathcal {P}}$ не лежали на одній сфері.

Комбінаторика в площині

Кожна тріангуляція будь-якої множини ${\mathcal {P}}$ з $n$ точок в площині має $2n-h-2$ трикутників і $3n-h-3$ ребер, де $h$ — кількість точок множини ${\mathcal {P}}$, що належать опуклій оболонці ${\mathcal {P}}$. Це випливає безпосередньо з формули Ейлера.

Алгоритми побудови тріангуляції у площині

Алгоритм розщеплення трикутника: Знайдіть опуклу оболонку множини точок ${\mathcal {P}}$ і тріангулюйте цю оболонку як багатокутник. Для кожної внутрішньої точки додайте ребра, які з'єднують її з трьома вершина трикутника, якому вона належить. Цей процес продовжується, доки не будуть вичерпані всі внутрішні точки.

Інкрементальний алгоритм: Відсортувати точки ${\mathcal {P}}$ за x-координатами. Перші три точки визначають трикутник. Розглянемо наступну точку $p$ в упорядкованому наборі і з'єднаємо її з усіма раніше розглянутими точками $\{p_{1},...,p_{k}\}$, які видно з точки $p$. Процес додавання по одній точці з ${\mathcal {P}}$, продовжується доки не будуть оброблені всі точки.

Часова складність різних алгоритмів

У наступній таблиці подано часову складність побудови тріангуляції множини точок із різними критеріями оптимальності у площині, де $n$ — кількість точок.

		мінімізувати	максимізувати
мінімум	кут		$O(n\log n)$ (тріангуляція Делоне)
максимум		$O(n^{2}\log n)$
мінімум	площа	$O(n^{2})$	$O(n^{2}\log n)$
максимум		$O(n^{2}\log n)$
максимум	степінь	NP-повна для степені 7
максимум	ексцентриситет	$O(n^{3})$
мінімум	довжина ребра	$O(n\log n)$ (найближча пара точок)	NP-повна
максимум		$O(n^{2})$	$O(n\log n)$ (за допомогою опуклої оболонки)
сума		NP-складний (тріангуляція мінімальної ваги)
мінімум	висота		$O(n^{2}\log n)$
максимум	нахил	$O(n^{3})$

Див. також

• Тріангуляція многокутника

Список літератури

• Bern, M.; Edelsbrunner, H.; Eppstein, D.; Mitchell, S.; Tan, T. S. (1993), Edge insertion for optimal triangulations, Discrete and Computational Geometry, 10 (1): 47—65, doi:10.1007/BF02573962, MR 1215322
• Chazelle, Bernard; Guibas, Leo J.; Lee, D. T. (1985). The power of geometric duality (PDF). BIT. BIT Computer Science and Numerical Mathematics. 25 (1): 76—90. doi:10.1007/BF01934990. ISSN 0006-3835. Архів оригіналу (PDF) за 17 вересня 2019. Процитовано 29 листопада 2019.
• de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry: Algorithms and Applications (вид. 3). Springer-Verlag. Архів оригіналу за 17 листопада 2011. Процитовано 29 листопада 2019.
• O'Rourke, Joseph; L. Devadoss, Satyan (2011). Discrete and Computational Geometry (вид. 1). Princeton University Press.
• Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1990). An O(n2log n) time algorithm for the MinMax angle triangulation. Proceedings of the sixth annual symposium on Computational geometry. SCG '90. ACM. с. 44—52. CiteSeerX 10.1.1.66.2895. doi:10.1145/98524.98535. ISBN 0-89791-362-0.
• Edelsbrunner, Herbert; Tan, Tiow Seng (1991). A quadratic time algorithm for the minmax length triangulation. 32nd Annual Symposium on Foundations of Computer Science. с. 414—423. CiteSeerX 10.1.1.66.8959. doi:10.1109/SFCS.1991.185400. ISBN 0-8186-2445-0.
• Fekete, Sándor P. (2012). «The Complexity of MaxMin Length Triangulation». arXiv:1208.0202v1 [cs.CG]. 
• Jansen, Klaus (1992). The Complexity of the Min-max Degree Triangulation Problem (PDF). 9th European Workshop on Computational Geometry. с. 40—43. Архів оригіналу (PDF) за 4 березня 2016. Процитовано 29 листопада 2019.
• Lloyd, Errol Lynn (1977). On triangulations of a set of points in the plane. 18th Annual Symposium on Foundations of Computer Science. Switching and Automata Theory, 1974., IEEE Conference Record of 15Th Annual Symposium on. с. 228—240. doi:10.1109/SFCS.1977.21. ISSN 0272-5428.
• Vassilev, Tzvetalin Simeonov (2005). Optimal Area Triangulation (PDF) (Ph.D.). University of Saskatchewan, Saskatoon. Архів оригіналу (PDF) за 13 серпня 2017. Процитовано 29 листопада 2019.