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