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

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

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

Определение

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

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

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

Докажем данное утверждение для n-мерного случая. Возьмём [math]a_1, a_2, ..., a_{n+1}[/math] афинно независимых точек и опишем вокруг них окружность с центром в точке [math]O[/math] и радиусом [math]R[/math]. Возьмём произвольную точку [math]x[/math], лежащую на расстоянии [math]tR[/math] от [math]O[/math], и посмотрим, как параметр [math]t[/math] влияет на положение её проекции на параболоид. Представим [math]\vec{a_i}[/math] как [math]\vec O + \vec{r_i}[/math], а [math]\vec x[/math] — как [math]\vec O + \vec{r_x}[/math]. Тогда проекции точек на параболоид будут выглядеть так: [math](\vec O + \vec{r_i}, (\vec O + \vec{r_i})^2) = (\vec O + \vec{r_i}, \vec O^2 + \vec{r_i}^2 + 2\vec O \vec {r_i}) = (\vec O + \vec{r_i}, \vec O^2 + R^2 + 2\vec O \vec {r_i})[/math] [math](\vec O + \vec{r_x}, (\vec O + \vec{r_x})^2) = (\vec O + \vec{r_x}, \vec O^2 + \vec{r_x}^2 + 2\vec O \vec {r_x}) = (\vec O + \vec{r_x}, \vec O^2 + (tR)^2 + 2\vec O \vec {r_x})[/math] Так как [math]\{r_i\}[/math] афинно независимы, то [math]r_x[/math] можно представить как [math]r_x = \sum_{i=1}^{n+1}\alpha_i r_i[/math], причём [math]\sum_{i=1}^{n+1}\alpha_i = 1[/math]. Запишем определитель, показывающий положение точки [math]x[/math] на параболоиде относительно плоскости, заданной точками [math]\{a_i\}[/math]: [math] \begin{vmatrix} O + r_1 & O^2 + R^2 + 2Or_1 & 1 \\ \vdots & \vdots & \vdots \\ O + r_{n+1} & O^2 + R^2 + 2Or_{n+1} & 1 \\ O + r_x & O^2 + (tR)^2 + 2Or_x & 1 \end{vmatrix} [/math] Умножим первые [math]n+1[/math] строк на [math]\alpha_i[/math] и вычтем из последней: [math] \begin{vmatrix} O + r_1 & O^2 + R^2 + 2Or_1 & 1 \\ \vdots & \vdots & \vdots \\ O + r_{n+1} & O^2 + R^2 + 2Or_{n+1} & 1 \\ r_x - \sum_{i=1}^{n+1}\alpha_i r_i & (tR)^2 - R^2 + 2O(r_x - \sum_{i=1}^{n+1}\alpha_i r_i) & 0 \end{vmatrix} = \begin{vmatrix} O + r_1 & O^2 + R^2 + 2Or_1 & 1 \\ \vdots & \vdots & \vdots \\ O + r_{n+1} & O^2 + R^2 + 2Or_{n+1} & 1 \\ 0 & R^2(t^2 - 1) & 0 \end{vmatrix} = R^2(t^2-1) \begin{vmatrix} O + r_1 & 1 \\ \vdots & \vdots \\ O + r_{n+1} & 1 \end{vmatrix} [/math] Из определителя видно, что, если [math]t \gt 1[/math] (точка [math]x[/math] лежит вне окружности), то определитель положителен, то есть точка [math]x[/math] лежит выше плоскости, заданной точками [math]\{a_i\}[/math]. Если же [math]t \lt 1[/math] (точка [math]x[/math] лежит внутри окружности), то определитель отрицателен, и точка [math]x[/math] лежит ниже плоскости. Если же точка лежит на окружности, то она попадает на ту же плоскость.

[math]\triangleleft[/math]

Теорема:

Подразбиение Делоне существует, причём для каждого набора точек оно единственно.

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

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

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

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

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

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

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

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

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

Средняя степень вершины в триангуляции — [math]O(1)[/math] ( TODO: Почему? — почти то, что нужно, здесь [1]. Потом пишем [math]\sum_{v \in V}{deg(v)} = 2E[/math], делим на [math]|V|[/math] и получаем [math]avg(deg(v)) = \frac{O(|V|)}{|V|} = O(1)[/math]), поэтому триангуляция звёздного многоугольника будет тоже за [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]\triangleleft[/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] — число пересечённых рёбер, и про то, что, если флипать что попало, можно нарваться на флип в невыпуклом многоугольнике

Удаление

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

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

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

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