355
правок
Изменения
м
→Время работы
Доказательство по индукции.
База. По [[#newedgeslemma|лемме7]] изначально не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точке.
Переход. Рассмотрим, что произойдёт с противолежащим точке <tex>V</tex> ребром <tex>AC</tex> после флипа, если оно плохое. До вставки точки <tex>V</tex> для триангуляции выполнялся глобальный критерий Делоне, поэтому в окружности, описанной вокруг треугольника <tex>ACD</tex>, не будет лежать никаких точек, кроме точки <tex>V</tex>. Можно построить окружность, касающуюся её изнутри в точке <tex>D</tex> и проходящую через точку <tex>V</tex>. В ней тоже не окажется никаких точек, так как она касается изнутри. Значит, для ребра <tex>VD</tex> выполняется критерий Делоне. Значит, после флипа ребро <tex>AC</tex> уже не будет флипаться. Так как для рёбер <tex>AV</tex> и <tex>CV</tex> выполняется критерий Делоне, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть рёбра, противолежащие точке <tex>V</tex>.
|id=flipnumberlemma
|proof=
Все флипнутые рёбра окажутся инцидентными вставленной точке, а [[#deglemma|степень вершины — <tex>O(1)</tex>(по лемме 9)]]. Поэтому будет сделано <tex>O(1)</tex> флипов.
}}
Так как среднее число флипов — <tex>O(1)</tex>, то время вставки целиком зависит от времени локализации.
