Перегляд вихідного коду сторінки Тріангуляція множини точок

[[Файл:PointSetTriangulations.svg|міні| Двв різні трикутники одного і того ж набору з 9 точок у площині. ]]
'''Тріангуляція множини точок''' <math>\mathcal{P}</math> в [[Евклідів простір|евклідовому просторі]] <math>\mathbb{R}^d</math>&nbsp;— це [[Симпліційний комплекс|симпліційний комплекс]], що охоплює [[Опукла оболонка|опуклу оболонку]] <math>\mathcal{P}</math>, і вершини якого належать <math>\mathcal{P}</math><ref name="DRS">{{Cite book|title=Triangulations, Structures for Algorithms and Applications|last=De Loera|first=Jesús A.|authorlink1=Jesús A. De Loera|last2=Rambau|first2=Jörg|last3=Santos|first3=Francisco|year=2010|series=Algorithms and Computation in Mathematics|publisher=Springer|volume=25}}</ref>. У [[Площина|площині]] (коли <math>\mathcal{P}</math>&nbsp;— це [[множина]] точок з <math>\mathbb{R}^2</math>), триангуляція складається з трикутників разом із їхніми ребрами та вершинами. Деякі автори вимагають, щоб усі точки <math>\mathcal{P}</math> були вершинами його тріангуляції{{Sfn|de Berg|van Kreveld|Overmars|Schwarzkopf|2008|місце=Section 9.1}}. У цьому випадку тріангуляція множини точок <math>\mathcal{P}</math> в площині можна також визначити як максимальний набір ребер, які не перетинаються та з'єднують точки <math>\mathcal{P}</math>. У площині, тріангуляція&nbsp;— це особливі випадки [[Плоский прямолінійний граф|плоских прямолінійних графів]].

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

Тріангуляція має численні застосування, та існує сенс у побудові «гарних» тріангуляцій множини точок за певними критеріями, наприклад, {{Нп|тріангуляція мінімальної ваги|||Minimum-weight triangulation}}. Іноді бажано мати тріангуляції зі спеціальними властивостями, наприклад, коли всі трикутники мають великі кути, що, в свою чергу, дозволяє уникнути довгих та вузьких «осколкових» трикутників<ref name="deBerg">{{Cite book|url=http://www.cs.uu.nl/geobook/interpolation.pdf|title=Computational Geometry: Algorithms and Applications|last=de Berg|first=Mark|authorlink1=Mark de Berg|last2=Otfried Cheong|authorlink2=Otfried Cheong|last3=Marc van Kreveld|last4=Mark Overmars|year=2008|publisher=Springer-Verlag|isbn=978-3-540-77973-5|id=|accessdate=29 листопада 2019|archive-date=28 жовтня 2009|archive-url=https://web.archive.org/web/20091028054315/http://www.cs.uu.nl/geobook/interpolation.pdf}}</ref>.

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

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

== Комбінаторика в площині ==
Кожна тріангуляція будь-якої множини <math>\mathcal{P}</math> з <math>n</math> точок в площині має <math> 2n - h - 2</math> трикутників і <math>3n - h - 3</math> ребер, де <math>h</math>&nbsp;— кількість точок множини <math>\mathcal{P}</math>, що належать [[Опукла оболонка|опуклій оболонці]] <math>\mathcal{P}</math>. Це випливає безпосередньо з [[Характеристика Ейлера|формули Ейлера]]<ref>{{Citation|last=Edelsbrunner|first=Herbert|author-link=Herbert Edelsbrunner|last2=Tan|first2=Tiow Seng|last3=Waupotitsch|first3=Roman|doi=10.1137/0913058|number=4|journal=SIAM Journal on Scientific and Statistical Computing|mr=1166172|pages=994–1008|title=An ''O''(''n''<sup>2</sup>&nbsp;log&nbsp;''n'') time algorithm for the minmax angle triangulation|volume=13|year=1992}}.</ref>.

== Алгоритми побудови тріангуляції у площині ==
'''Алгоритм розщеплення трикутника''':
Знайдіть опуклу оболонку множини точок <math>\mathcal{P}</math> і [[Тріангуляція многокутника|тріангулюйте]] цю оболонку як багатокутник. Для кожної внутрішньої точки додайте ребра, які з'єднують її з трьома вершина трикутника, якому вона належить. Цей процес продовжується, доки не будуть вичерпані всі внутрішні точки<ref>Devadoss, O'Rourke ''Discrete and Computational Geometry''. Princeton University Press, 2011, p. 60.</ref>.

'''Інкрементальний алгоритм''':
Відсортувати точки <math>\mathcal{P}</math> за x-координатами. Перші три точки визначають [[трикутник]]. Розглянемо наступну точку <math>p</math> в упорядкованому наборі і з'єднаємо її з усіма раніше розглянутими точками <math>\{p_1,..., p_k\}</math>, які видно з точки <math>p</math>. Процес додавання по одній точці з <math>\mathcal{P}</math>, продовжується доки не будуть оброблені всі точки<ref>Devadoss, O'Rourke ''Discrete and Computational Geometry''. Princeton University Press, 2011, p. 62.</ref>.

== Часова складність різних алгоритмів ==
У наступній таблиці подано [[Часова складність алгоритму|часову складність]] побудови тріангуляції множини точок із різними критеріями оптимальності у площині, де <math>n</math>&nbsp;— кількість точок.
{| class="wikitable" style="border:none;text-align:center;"
! colspan="2" style="background: white;border: none;" |
! style="padding:1em;" | мінімізувати
! style="padding:1em;" | максимізувати
|-
! style="padding:1em;" | мінімум
! rowspan="2" style="padding:1em;" | кут
| bgcolor="darkgray" |
| <math>O(n \log n)</math><br/> ([[тріангуляція Делоне]])
|-
! style="padding:1em;" | максимум
|<math>O(n^2 \log n)</math>{{Sfn|Edelsbrunner|Tan|Waupotitsch|1990}}{{Sfn|Bern|Edelsbrunner|Eppstein|Mitchell|1993}}
| bgcolor="darkgray" |
|-
! style="padding:1em;" | мінімум
! rowspan="2" style="padding:1em;" | площа
|<math>O(n^2)</math>{{Sfn|Chazelle|Guibas|Lee|1985}}
|<math>O(n^2 \log n)</math>{{Sfn|Vassilev|2005}}
|-
! style="padding:1em;" | максимум
|<math>O(n^2 \log n)</math>{{Sfn|Vassilev|2005}}
| bgcolor="darkgray" |
|-
! style="padding:1em;" | максимум
! rowspan="1" style="padding:1em;" | [[Степінь вершини (теорія графів)|степінь]]
| [[NP-повна задача|NP-повна]] <br/> для степені 7{{Sfn|Jansen|1992}}
| bgcolor="darkgray" |
|-
! style="padding:1em;" | максимум
! rowspan="1" style="padding:1em;" | [[Словник_термінів_теорії_графів#Е|ексцентриситет]]
|<math>O(n^3)</math>{{Sfn|Bern|Edelsbrunner|Eppstein|Mitchell|1993}}
| bgcolor="darkgray" |
|-
! style="padding:1em;" | мінімум
! rowspan="3" style="padding:1em;" | довжина ребра
| <math>O(n \log n)</math><br/> ([[найближча пара точок]])
| [[NP-повна задача|NP-повна]]{{Sfn|Fekete|2012}}
|-
! style="padding:1em;" | максимум
|<math>O(n^2)</math>{{Sfn|Edelsbrunner|Tan|1991}}
| <math>O(n \log n)</math><br/> (за допомогою [[Алгоритми обчислення опуклої оболонки|опуклої оболонки]])
|-
! style="padding:1em;" | сума
| [[NP-складна задача|NP-складний]] <br/> ({{Нп|тріангуляція мінімальної ваги|||Minimum-weight triangulation}})
| bgcolor="darkgray" |
|-
! style="padding:1em;" | мінімум
! rowspan="1" style="padding:1em;" | висота
| bgcolor="darkgray" |
|<math>O(n^2 \log n)</math>{{Sfn|Bern|Edelsbrunner|Eppstein|Mitchell|1993}}
|-
! style="padding:1em;" | максимум
! rowspan="1" style="padding:1em;" | нахил
|<math>O(n^3)</math>{{Sfn|Bern|Edelsbrunner|Eppstein|Mitchell|1993}}
| bgcolor="darkgray" |
|}

== Див. також ==
* [[Тріангуляція многокутника]]

== Примітки ==
{{Reflist|30em}}

== Список літератури ==
{{refbegin|colwidth=30em}}
* {{citation|last1=Bern|first1=M.|last2=Edelsbrunner|first2=H.|author2-link=Herbert Edelsbrunner|last3=Eppstein|first3=D.|author3-link=David Eppstein|last4=Mitchell|first4=S.|last5=Tan|first5=T. S.|doi=10.1007/BF02573962|issue=1|journal=[[Discrete and Computational Geometry]]|mr=1215322|pages=47–65|title=Edge insertion for optimal triangulations|volume=10|year=1993|ref=harv}}
* {{cite journal|last1=Chazelle|first1=Bernard|last2=Guibas|first2=Leo J.|last3=Lee|first3=D. T.|year=1985|title=The power of geometric duality|url=http://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf|journal=BIT|publisher=BIT Computer Science and Numerical Mathematics|volume=25|issue=1|pages=76–90|doi=10.1007/BF01934990|issn=0006-3835|ref=harv|accessdate=29 листопада 2019|archive-date=17 вересня 2019|archive-url=https://web.archive.org/web/20190917063844/https://www.cs.princeton.edu/~chazelle/pubs/PowerDuality.pdf}}
* {{cite book|url=http://www.cs.uu.nl/geobook/|title=Computational Geometry: Algorithms and Applications|last1=de Berg|first1=Mark|last2=van Kreveld|first2=Marc|last3=Overmars|first3=Mark|last4=Schwarzkopf|first4=Otfried|year=2008|publisher=Springer-Verlag|edition=3|ref=harv|accessdate=29 листопада 2019|archive-date=17 листопада 2011|archive-url=https://web.archive.org/web/20111117042433/http://www.cs.uu.nl/geobook/}}
* {{cite book|title=Discrete and Computational Geometry|url=https://archive.org/details/discretecomputat0000deva|last1=O'Rourke|first1=Joseph|last2=L. Devadoss|first2=Satyan|year=2011|publisher=Princeton University Press|edition=1|ref=dcg|author2-link=Satyan Devadoss}}
* {{cite conference|last1=Edelsbrunner|first1=Herbert|last2=Tan|first2=Tiow Seng|last3=Waupotitsch|first3=Roman|year=1990|title=An O(n2log n) time algorithm for the MinMax angle triangulation|conference=Proceedings of the sixth annual symposium on Computational geometry|series=SCG '90|pages=44–52|isbn=0-89791-362-0|doi=10.1145/98524.98535|publisher=ACM|ref=harv|citeseerx=10.1.1.66.2895}}
* {{cite conference|last1=Edelsbrunner|first1=Herbert|last2=Tan|first2=Tiow Seng|year=1991|title=A quadratic time algorithm for the minmax length triangulation|conference=32nd Annual Symposium on Foundations of Computer Science|pages=414–423|url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=185400|isbn=0-8186-2445-0|doi=10.1109/SFCS.1991.185400|ref=harv|citeseerx=10.1.1.66.8959}}
* {{cite arXiv|last=Fekete|first=Sándor P.|eprint=1208.0202v1|title=The Complexity of MaxMin Length Triangulation|year=2012|ref=harv|class=cs.CG}}
* {{cite conference|last=Jansen|first=Klaus|year=1992|title=The Complexity of the Min-max Degree Triangulation Problem|conference=9th European Workshop on Computational Geometry|pages=40–43|url=http://tizian.cs.uni-bonn.de/EuroCG93/j-cmmdt-93.pdf|ref=harv|accessdate=29 листопада 2019|archive-date=4 березня 2016|archive-url=https://web.archive.org/web/20160304040655/http://tizian.cs.uni-bonn.de/EuroCG93/j-cmmdt-93.pdf}}
* {{cite conference|last=Lloyd|first=Errol Lynn|year=1977|title=On triangulations of a set of points in the plane|journal=Switching and Automata Theory, 1974., IEEE Conference Record of 15Th Annual Symposium on|conference=18th Annual Symposium on Foundations of Computer Science|pages=228–240|url=http://ieeexplore.ieee.org/xpl/articleDetails.jsp?arnumber=4567947|issn=0272-5428|doi=10.1109/SFCS.1977.21|ref=harv}}
* {{cite thesis|type=Ph.D.|first=Tzvetalin Simeonov|last=Vassilev|title=Optimal Area Triangulation|publisher=University of Saskatchewan, Saskatoon|year=2005|url=http://ecommons.usask.ca/bitstream/handle/10388/etd-08232005-111957/thesisFF.pdf|ref=harv|accessdate=29 листопада 2019|archive-date=13 серпня 2017|archive-url=https://web.archive.org/web/20170813183040/https://ecommons.usask.ca/bitstream/handle/10388/etd-08232005-111957/thesisFF.pdf}}
{{refend}}

[[Категорія:Дискретна геометрія]]
[[Категорія:Обчислювальна геометрія]]