264
правки
Изменения
м
→Динамический алгоритм
}}
==Динамический алгоритм==
{{Определение
|definition=
Рассмотрим пару смежных треугольников. Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется '''flip''' ('''флип''').
}}
Из [[#fliplemma|леммы 3]] следует, что если ребро плохое, то флип сделает его хорошим.
{{Лемма
|about=5
|statement=Флип плохого ребра уменьшает разность объёмов сферы и выпуклого многогранника, построенного на точках с заданными ребрами.
|id=volumelemma
|proof=
Рассмотрим два таких смежных треугольника, что ребро между ними является плохим.Четыре точки, принадлежащие смежным треугольникам, образуют тетраэдр.
Проведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит выше этой плоскости (так как для плохого ребра не выполняется локальный критерий Делоне), то есть тетраэдр не включается в объем фигуры.
После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.
}}
{{Лемма
|about=6
|statement=
Флипами можно достичь хорошей триангуляции за конечное время.
|proof=
Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов сферы и многогранника, постоенного по триангуляции убывает ([[#volumelemma|по лемме 5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.
}}
===Вставка точки===
===Удаление точки===
