355
правок
Изменения
→Динамическая триангуляция
|proof=
Очевидно, потому что каждый флип уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
}}
{{Лемма
|statement=
Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.
|id=newedgeslemma
|proof=
[[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]
Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. Проведём касательную к этой окружности в точке <tex>C</tex>. На ребре <tex>VC</tex> можно построить окружность с той же касательной. Эта окружность целиком лежит в окружности, описанной вокруг треугольника, значит, в ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значит, оно хорошее.
Случай, когда точка вставляется на ребро, рассматривается аналогично.
}}
=== Вставка точки ===
Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых.
Итого у нас появилось несколько новых рёбер. Они все хорошие ({{TODOпо [[#goodedgeslemma|t=Доказать, почему}}лемме]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.
Среднее число флипов — <tex>O(1)</tex> ({{TODO|t=Доказать, почему}}). Поэтому время вставки целиком зависит от времени локализации.
