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

Конспект написан не до конца, но основные вещи уже есть.

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

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

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

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

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

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

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

Берём четыре лежащих на окружности точки, проецируем на параболоид, считаем определитель, видим, что получается ноль. Профит.

[math]\triangleleft[/math]

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

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

Спроецируем четыре точки на параболоид. Очевидно, что по ним можно построить четырёхугольник двумя способами: в первом случае он будет «вогнутым», во втором — «выпуклым». По доказанному выше факту про окружность, спроецированную на параболоид, выпуклое ребро будет хорошим.

[math]\triangleleft[/math]

Лемма:

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

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

[math]\triangleright[/math]

Ну предположим, что это не так, то есть все рёбра хорошие, но существует треугольник, описанная окружность которого содержит какие-либо точки триангуляции. Тогда очевидно, что одно из рёбер этого треугольника окажется плохим. Противоречие.

[math]\triangleleft[/math]

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

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

Из первой леммы следует, что, если ребро плохое, то флип сделает его хорошим.

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

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

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

Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы.

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

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

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

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

Локализационная структура

Сама структура

В общем-то, довольно стандартная схема для рандомизированных структур: на нижнем уровне содержатся все точки; каждая точка с вероятностью p проходит на следующий уровень.

Локализация

Как происходит локализация: нам дают точку [math]v_{i+1}[/math], которая на предыдущем уровне была ближайшей к точке [math]q[/math], которую мы локализуем. Нужно получить следующую точку [math]v_i[/math], которая будет ближайшей уже на этом уровне. Делается это следующим образом:

• Находим, в каком из треугольников, смежных с [math]v_{i+1}[/math], лежит отрезок [math]v_{i+1} q[/math]
• Находим, какие рёбра треугольников пересекает [math]v_{i+1} q[/math], в итоге находим треугольник, в котором лежит [math]q[/math]
• Находим ближайшую к [math]q[/math] точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к [math]q[/math] вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к [math]q[/math] — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая.

Теорема:

Данный алгоритм найдёт ближайшую точку.

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

[math]\triangleright[/math]

TODO: Картинку для ясности Предположим, что это не так. Назовём локализуемую точку [math]q[/math], а последнего кандидата на то, чтобы быть ближайшей точкой — [math]v[/math]. Раз эта точка на самом деле не ближайшая, то в окружности, проходящей через [math]v[/math], с центром в точке [math]q[/math] найдутся ещё какие-то точки, не смежные с [math]v[/math]. Рассмотрим ближайшую из них к [math]v[/math]: точку [math]v'[/math]. Построим на [math]vv'[/math] окружность как на диаметре. В этой окружности не будет лежать никаких точек, так как мы взяли ближайшую. Значит, ребро [math]vv'[/math] удовлетворяет критерию Делоне и должно являться ребром триангуляции, но по предположению этого ребра нет. Значит, предположение неверно.

[math]\triangleleft[/math]

Профит

TODO: Время работы, требуемая память

Constraints

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

Констрейнты — рёбра, которые нельзя флипать

Утверждение:

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

Вставка

Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом ( TODO: Картинку бы), и флипаем их. Последнее флипнутое ребро и будет констрейнтом (по понятным причинам), после флипа пометим его как констрейнт. Понятное дело, критерий «хорошести» ребра при таких фокусах немного изменится: туда добавится проверка на то, не является ли ребро констрейнтом. Затем флипаем всё, что могло стать плохим (кроме констрейнта), пока триангуляция вновь не станет условно хорошей.

TODO: Тут должно быть ещё несколько упоительных фактов про то, что вставка производится за [math]O(k^2)[/math], где [math]k[/math] — число пересечённых рёбер, и про то, что, если флипать что попало, можно нарваться на флип в невыпуклом многоугольнике

Удаление

Аналогично: помечаем ребро как не-констрейнт и начинаем флипать, пока не дойдём до хорошей (или условно хорошей) триангуляции.

Работает оно столько же, сколько и вставка, ибо всё, что мы нафлипали при вставке, нужно перефлипать обратно.

Констрейнты в локализационной структуре

В локализационную структуру констрейнты нужно вставлять только на нижний уровень, ибо выше они нафиг не нужны.