264
правки
Изменения
→Удаление точки
Если бы мы могли видеть грани, находящиеся вне нашего звездного многоугольника, то это бы значило, что от удаляемой вершины до вершины, противолежащей ребру звездного многоугольника и лежащей в этой грани можно было бы провести ребро. Которого изначально не было.И это ребро лежало бы вне нашего многогранника, что противоречило бы его выпуклости.
}}
Понятно, что мы постепенно перестаем видеть какие-то грани.Это происходит когда мы уходим ближе к центру, чем плоскость, соответствующая грани.
{{Теорема
|statement= Когда мы перестаем видеть грани, они исчезают в порядке, соответствующем отрезанию выделению их как ушей у звездного многоугольникав новой триангуляции.
|id=deleteteorem
|proof=# Расмотрим случай, когда у нас никакие четыре точки в звездном многоугольнике не лежат на одной окружности. Это значит, что все грани выпуклой оболочки будут треугольниками.
Ухом является часть, которая по двум ребрам граничит с невидимыми гранями и по одному ребру может граничить с видимой.
Посмотрим в каком порядке исчезают грани.
Этот отрезок будет виден. Он не будет лежать на плоскоси. Он не будет лежать под плоскостью. Тогла получается, что он лежит над плоскостью(ближе к краю сферы), значит, многогранник был невыпуклый.
Получается, что грань ушла и у нее только один видимый сосед. Мы можем выделить грань как ухо.
# Общий случай, когда четыре точки в звездном многоугольнике могут лежать на одной окружности рассматривается аналогично.
}}
===Алгоритм удаления точки===
# Уберем точку.
# Сделаем приоритетную очередь, в которой будем хранить пары отрезков, образующие ухо. Для этой очереди будем использовать TODO предикат, сортирующий уши в порядке, в котором они пересекают луч по направлению от удаляемой точки к центру сферы.
# На очередном шаге достаем ухо, отделяем его.
# Добавляем в очередь получившиеся новые уши.
===Время работы===
Если наш звездный многоугольник состоит из <tex>k</tex> точек, то на один запрос приоритетной очереди будет уходить <tex> \mathcal{O}(\log(k)) </tex> операций. Значит общая ассимптотика будет <tex> \mathcal{O}(k \log(k)) </tex>.
===Локализация в триангуляции===
