68
правок
Изменения
→Динамический алгоритм
Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов сферы и многогранника, постоенного по триангуляции убывает ([[#volumelemma|по лемме 5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.
}}
{{Лемма
|about=7
|id=1
|statement=Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.
|proof=
[[Файл:Lemma7.jpg|300px|thumb|right|Точка <tex>P</tex> вставлена в треугольник]] Пусть мы вставляем точку <tex>P</tex>. Предположим, она была вставлена в треугольник <tex>ABC</tex> не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>PC</tex>. Тогда проведем через точки <tex>A</tex>, <tex>B</tex>, <tex>C</tex> плоскость <tex>\alpha</tex>, а так же проведем касательную плоскость <tex>\beta</tex> к сфере через точку <tex>C</tex>. Начнем уменьшать между этими плоскостями угол, двигая <tex>\alpha</tex> к <tex>\beta</tex>. В какой-то момент <tex>\alpha</tex> пересечет точку <tex>P</tex>, а тогда мы предоставили плоскость, от которой все точки триангуляции находятся по одну сторону, так как изначально выше <tex>\alpha</tex> была только точка <tex>P</tex>, а значит, ребро <tex>PC</tex> удовлетворяет глобальному критерию Делоне. Аналогично для ребер <tex>PA</tex> и <tex>PB</tex>.
Случай, когда точка вставляется на ребро, рассматривается аналогично.
}}
===Вставка точки===
===Удаление точки===
