Изменения

Перейти к: навигация, поиск

Триангуляция Делоне на сфере

12 байт убрано, 04:08, 22 ноября 2016
м
Динамический алгоритм
|statement=Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.
|proof=
[[Файл:Lemma7.jpg|300px|thumb|right|Точка <tex>P</tex> вставлена в треугольник]] Пусть мы вставляем точку <tex>P</tex>. Предположим, она была вставлена в треугольник <tex>ABC</tex> не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>PC</tex>. Тогда проведем через точки <tex>A</tex>, <tex>B</tex>, <tex>C</tex> плоскость <tex>\alpha</tex>, а так же проведем касательную плоскость <tex>\beta</tex> к сфере через точку <tex>C</tex>. Начнем уменьшать между этими плоскостями угол, двигая <tex>\alpha</tex> к <tex>\beta</tex>. В какой-то момент <tex>\alpha</tex> пересечет точку <tex>P</tex>, а тогда мы предоставили плоскость, от которой все точки триангуляции находятся по одну сторону, так как изначально выше <tex>\alpha</tex> была только точка <tex>P</tex>, а значит, ребро <tex>PC</tex> удовлетворяет глобальному критерию Делоне. Аналогично для ребер <tex>PA</tex> и <tex>PB</tex>.
Случай, когда точка вставляется на ребро, рассматривается аналогично.
23
правки

Навигация