Изменения

Как следует из теоремыДополним множество наших точек, точкой <tex>O</tex>, являющейся центром сферы. Данная точка нам понадобится, для тогоесли все точки оказались в одной полусфере.(более быстрая проверка, чтобы построить триангуляцию Делоне на множестве точек на сфере нам необходимо:то какие треугольники надо исключить, чем подсчет предиката).# Построить Построим для данного множества выпуклую оболочку заданного набора точек# Пройтись Удалим все треугольники, которые содеражат вершину <tex>O</tex> (это обязательно будут треугольники и они будут существовать только в том случае, если точки лежат в одной полусфере)# Пройдемся по всем "выжившим" граням получившейся выпуклой оболочки и, если грань не является треугольником, то нужно затриангулировать ее как нибудьтриангулируем их. ===Корректность===Корректность следует из теорем выше.

Мы можем построить выпуклую оболочку за <tex> \mathcal{O}(n N \log(nN)) </tex>, где <tex>nN</tex> {{---}} количество точек.Триангуляция выпуклого многоугольника требует времени Удалить треугольники мы можем за <tex> \mathcal{O}(kN) </tex>, где <tex>k</tex> {{---}} число вершин с многоугольнике. Следовательно, в худшем случае нам потребуется суммарно Триангулиравать грани мы можем за <tex> \mathcal{O}(nN) </tex> операции, чтоб перетриангулировать все грани, оказавшиеся многоугольниками после построения выпуклой оболочкикак было доказано выше.Таким образом, время работы всего алгоритма будет Итого : <tex> \mathcal{O}(n N \log(nN)) </tex>,