355
правок
Изменения
м
→Время работы
Переход. Рассмотрим, что произойдёт с противолежащим точке <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>.
}}
{{Лемма
|statement=
Средняя степень вершины после вставки её в триангуляцию Делоне равна <tex>O(1)</tex>.
|id=deglemma
|proof=
{{TODO|t=proof}}
}}
{{Теорема
При вставке точки в триангуляцию Делоне в среднем придётся сделать <tex>O(1)</tex> флипов.
|proof=
Все флипнутые рёбра окажутся инцидентными вставленной точке, а [[#deglemma|степень вершины — <tex>O(1)</tex>]]. Поэтому будет сделано <tex>O(1)</tex> флипов.
}}
Так как среднее число флипов — <tex>O(1)</tex>, то время вставки целиком зависит от времени локализации.
