264
правки
Изменения
м
→Существования триангуляции Делоне
Если случилось так, что у нас есть четыре или более точек, лежащих на одной окружности, то у построенной выпуклой оболочки, возможно, будут грани, не являющиеся треугольниками. Понятно, что такие грани будут выпуклыми многоугольниками. Тогда каждую из них можно затриангулировать [[Триангуляция полигонов (ушная + монотонная)|методом отрезания "ушей"]]. Получившиеся треугольники будут лежать в одной плоскости и,следовательно, не будут нарушать критерий Делоне.
В этом случае триангуляция может быть не единственна.
===Время работы===
Мы можем построить выпуклуюоболочку за <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>
