355
правок
Изменения
Нет описания правки
}}
Грани выпуклой оболочки — фигуры подразбиения Делоне. По лемме очевидно, что внутри описанных окружностей не будет лежать никаких точек. Так же очевидно, что такое подразбиение единственно. Затриангулировав фигуры подразбиения Делоне, получим триангуляцию Делоне, которая так же будет единственна (с точностью до подразбиения Делоне).
== Некоторые упоительные факты ==
{{Определение
|definition=Ребро назовём '''хорошим''', если для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот)
}}
{{Лемма
|statement=
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее
|proof=
{{TODO|t=Доказать}}
}}
{{Лемма
|statement=
Если все рёбра хорошие, то и триангуляция хорошая
|proof=
{{TODO|t=Доказать}}
}}
{{Определение
|definition=
Для пары смежных треугольников '''flip''' — убирание смежного ребра и проведение другого
}}
{{Лемма
|statement=
Флипами можно достичь хорошей триангуляции за конечное время
|proof=
{{TODO|t=Доказать}}
}}
== Динамическая триангуляция ==
=== Вставка точки ===
=== Удаление точки ===
== Локализация в триангуляции ==
== Constraints ==
