68
правок
Изменения
→Вставка точки
===Вставка точки===
{{Лемма
|about=8
|statement=
При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.
|proof=Доказательство по индукции.
База. По [[#newedgeslemma|лемме 7]] изначально не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точке.
Переход. Пусть мы вставили точку <tex>P</tex>. Рассмотрим, что произойдёт с противолежащим ей ребром <tex>AC</tex> после флипа, если оно плохое. До вставки точки <tex>P</tex> для триангуляции выполнялся глобальный критерий Делоне, поэтому плоскость <tex>\alpha</tex>, проходящая через точки <tex>A</tex>, <tex>C</tex> и <tex>D</tex> содержала все точки по одну сторону от себя, теперь же по другую сторону еще будет только точка <tex>P</tex>. Проведем плоскость <tex>\beta</tex> через точки <tex>P</tex> и <tex>D</tex> так, что линия пересечения <tex>\alpha</tex> и <tex>\beta</tex> лежала бы в одной плоскости с касательной на сфере через точку <tex>D</tex> к окружности, проходящей через точки <tex>A</tex>, <tex>C</tex> и <tex>D</tex>. Тогда уменьшая угол между этими плоскостями, двигая <tex>\alpha</tex> к <tex>\beta</tex>, найдем момент, когда <tex>\alpha</tex> пересечет точку <tex>P</tex>, а значит, в окружности, отсекаемой в этот момент плоскостью <tex>\alpha</tex> не будет никаких точек. Значит, ребро <tex>PD</tex> хорошее. Значит, после своего флипа ребро <tex>AC</tex> уже не будет флипаться. Так как для рёбер <tex>AP</tex> и <tex>CP</tex> выполняется критерий Делоне, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть рёбра, противолежащие точке <tex>P</tex>.
}}
{{Лемма
|about=О степени вершины
