264
правки
Изменения
м
→Существования триангуляции Делоне
Если случилось так, что у нас есть четыре или более точек, лежащих на одной окружности, то у построенной выпуклой оболочки, возможно, будут грани, не являющиеся треугольниками. Понятно, что такие грани будут выпуклыми многоугольниками. Тогда каждую из них можно затриангулировать [[Триангуляция полигонов (ушная + монотонная)|методом отрезания "ушей"]]. Получившиеся треугольники будут лежать в одной плоскости и,следовательно, не будут нарушать критерий Делоне.
В этом случае триангуляция может быть не единственна.
==Статический алгоритм==
===Алгоритм===
Как следует из теоремы, для того, чтобы построить триангуляцию Делоне на множестве точек на сфере нам необходимо:
1) построить выпуклую оболочку заданного набора точек
2) пройтись по граням получившейся выпуклой оболочки и, если грань не является треугольником, то нужно затриангулировать ее как нибудь.
===Время работы===
Мы можем построить выпуклую оболочку за <tex> \mathcal{O}(n \log(n)) </tex>, где <tex>n</tex> {{---}} количество точек.
Триангуляция выпуклого многоугольника требует времени <tex> \mathcal{O}(k) </tex>, где <tex>k</tex> {{---}} число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно <tex> \mathcal{O}(n) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочки.
Таким образом, время работы всего алгоритма будет <tex> \mathcal{O}n \log(n) </tex>
== Критерий Делоне для ребер==
{{Определение
