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