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

Конспект не готов.

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше?

Что такое триангуляция Делоне

Определение:

Подразбиение Делоне — такое разбиение плоскости на множество выпуклых фигур, что в окружности, описанной вокруг любой из фигур, не находится никаких точек.

Определение:

Триангуляция Делоне — триангуляция, являющаяся подразбиением Делоне.

Существование триангуляции Делоне

Откуда нам знать, что такое подразбиение вообще существует?

Спроецируем нашу плоскость на параболоид и построим трёхмерную выпуклую оболочку множества точек.

Лемма:

Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.

Доказательство:

[math]\triangleright[/math]

TODO: Янизнаюололо

[math]\triangleleft[/math]

Грани выпуклой оболочки — фигуры подразбиения Делоне. По лемме очевидно, что внутри описанных окружностей не будет лежать никаких точек. Так же очевидно, что такое подразбиение единственно. Затриангулировав фигуры подразбиения Делоне, получим триангуляцию Делоне, которая так же будет единственна (с точностью до подразбиения Делоне).

Некоторые упоительные факты

Определение:

Ребро назовём хорошим, если для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот)

Лемма:

Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее

Доказательство:

[math]\triangleright[/math]

TODO: Доказать

[math]\triangleleft[/math]

Лемма:

Если все рёбра хорошие, то и триангуляция хорошая

Доказательство:

[math]\triangleright[/math]

TODO: Доказать

[math]\triangleleft[/math]

Определение:

Для пары смежных треугольников flip — убирание смежного ребра и проведение другого

Лемма:

Флипами можно достичь хорошей триангуляции за конечное время

Доказательство:

[math]\triangleright[/math]

TODO: Доказать

[math]\triangleleft[/math]

Динамическая триангуляция

Вставка точки

Вставка точки, лежащей внутри триангуляции

TODO: Надо бы вставить сюда картинки

Для начала локализуемся: поймём, в каком фейсе лежит точка (или на каком ребре). Вставляем. Итого у нас появилось несколько новых рёбер. Они все хорошие ( TODO: Доказать, почему), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.

Среднее число флипов — [math]O(1)[/math] ( TODO: Доказать, почему). Поэтому время вставки целиком зависит от времени локализации.

Вставка точки, лежащей снаружи триангуляции

TODO: Написать про бесконечно удалённую точку

Удаление точки

При удалении точки получится звёздный многоугольник, который можно затриангулировать за линию. Дальше по традиции флипаем всё, что могло стать плохим, пока не получим хорошую триангуляцию.

Средняя степень вершины в триангуляции — [math]O(1)[/math] ( TODO: Почему?), поэтому триангуляция звёздного многоугольника будет тоже за [math]O(1)[/math]. С флипами всё тоже, в общем-то, хорошо. Итого удаление точки работает за [math]O(1)[/math].