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

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

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

Определение

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

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

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

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

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

Лемма:

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

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

[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]\{a_i\}[/math] и от знака [math]t^2-1[/math]. Для определённости будем считать, что точки [math]\{a_i\}[/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]

Для рёбер AB и CD выполняется критерий Делоне, на них построены окружности То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне). Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне. Предположим, что это ребро (назовём его [math]AB[/math]) не принадлежит триангуляции Делоне. Тогда существует пересекающее его ребро [math]CD[/math], принадлежащее триангуляции. Рассмотрим четырёхугольник [math]ACBD[/math]. Точки [math]C[/math] и [math]D[/math] лежат вне окружности, построенной на [math]AB[/math] как на хорде, поэтому сумма углов [math]C[/math] и [math]D[/math] меньше 180°. Аналогичным образом доказывается, что сумма углов [math]A[/math] и [math]B[/math] тоже меньше 180°. Значит, сумма углов четырёхугольника [math]ACBD[/math] меньше 360°, что невозможно. Противоречие. Значит, ребро [math]AB[/math] принадлежит триангуляции Делоне.

[math]\triangleleft[/math]

Локальный критерий Делоне

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

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

Будем называть хорошими те рёбра, для которых выполняется локальный критерий Делоне.

Лемма:

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

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

[math]\triangleright[/math]

Рёбра AB и BC плохие Предположим, что это не так, то есть оба ребра (назовём их [math]AB[/math] и [math]CD[/math]) плохие. Рассмотрим четырёхугольник [math]ACBD[/math] и окружность, описанную вокруг треугольника [math]ABC[/math]. Точка [math]D[/math] лежит внутри этой окружности, значит, сумма углов [math]C[/math] и [math]D[/math] больше 180°. Аналогично доказывается, что сумма углов [math]A[/math] и [math]B[/math] больше 180°. Значит, сумма углов четырёхугольника [math]ACBD[/math] больше 360°, что невозможно.

[math]\triangleleft[/math]

Лемма:

Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоне.

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

[math]\triangleright[/math]

Все рёбра треугольника хорошие, но описанная окружность содержит точки Предположим, что это не так, то есть все рёбра хорошие, но существует треугольник, описанная окружность которого содержит какие-либо точки триангуляции. Рассмотрим ребро (пусть это будет [math]BC[/math]), отрезающее сегмент, содержащий точки, и выберем из этих точек такую точку [math]D[/math], что угол [math]BDC[/math] максимален. Так как угол [math]BDC[/math] максимален, то точка [math]D[/math] является вершиной смежного с [math]ABC[/math] треугольника (в противном случае в треугольнике [math]BCD[/math] будут лежать какие-либо точки, что невозможно по построению). Значит, ребро [math]BC[/math] плохое, что противоречит условию. Значит, предположение неверно.

[math]\triangleleft[/math]

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

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

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

Красное ребро — до флипа, синее — после

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

Лемма:

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

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

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

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

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

Вставка в треугольник

Вставка на ребро

Для начала локализуемся: поймём, в каком фейсе лежит точка (или на каком ребре).

Если точка лежит внутри фейса, добавляем три ребра, сам фейс превращаем в один из новых смежных с вставляемой точкой и добавялем ещё два фейса.

Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых.

Итого у нас появилось несколько новых рёбер. Они все хорошие ( 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]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] — число пересечённых рёбер, и про то, что, если флипать что попало, можно нарваться на флип в невыпуклом многоугольнике

Удаление

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

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

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

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