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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також

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

Примітки

1. De Loera, Jesús A.; Rambau, Jörg; Santos, Francisco (2010). Triangulations, Structures for Algorithms and Applications. Algorithms and Computation in Mathematics. Т. 25. Springer.
2. de Berg та ін., 2008, Section 9.1.
3. de Berg, Mark; Otfried Cheong; Marc van Kreveld; Mark Overmars (2008). Computational Geometry: Algorithms and Applications (PDF). Springer-Verlag. ISBN 978-3-540-77973-5. Архів оригіналу (PDF) за 28 жовтня 2009. Процитовано 29 листопада 2019.
4. Lloyd, 1977.
5. Edelsbrunner, Herbert; Tan, Tiow Seng; Waupotitsch, Roman (1992), An O(n^2 log n) time algorithm for the minmax angle triangulation, SIAM Journal on Scientific and Statistical Computing, 13 (4): 994—1008, doi:10.1137/0913058, MR 1166172.
6. Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 60.
7. Devadoss, O'Rourke Discrete and Computational Geometry. Princeton University Press, 2011, p. 62.
8. Edelsbrunner, Tan та Waupotitsch, 1990.
9. Bern та ін., 1993.
10. Chazelle, Guibas та Lee, 1985.
11. Vassilev, 2005.
12. Jansen, 1992.
13. Fekete, 2012.
14. Edelsbrunner та Tan, 1991.

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

• 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.