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