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

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

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

TODO: Перенумеровать леммы

Определение

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

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

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

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

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

Лемма (1):

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

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

[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]

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

[math]\triangleleft[/math]

Критерий Делоне для рёбер

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

Критерий Делоне для ребра: на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.

Лемма (2):

Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.

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

[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]

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

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

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

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

Лемма (3):

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

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

[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]

Лемма (4):

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

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

[math]\triangleright[/math]

Все рёбра треугольника хорошие, но описанная окружность содержит точки Предположим, что это не так, то есть все рёбра хорошие, но существуют треугольники, описанная окружность которых содержат какие-либо точки триангуляции. Возьмём какую-либо конфликтную точку [math]E[/math]. Рассмотрим такой треугольник [math]ABC[/math] из тех, в описанную окружность которых попадает [math]E[/math], что угол [math]BEC[/math] максимален, если [math]BC[/math] — ближайшая к точке [math]E[/math] сторона. Пусть треугольник [math]BDC[/math] — смежный с [math]ABC[/math]. Докажем, что точка [math]E[/math] лежит в окружности, описанной вокруг [math]BDC[/math]. Предположим, что это не так. Посмотрим на окружность, описанную вокруг треугольника [math]ABC[/math]: [math]\angle BAC + \angle BEC \gt 180^\circ[/math] и [math]\angle BAC + \angle BDC \lt 180^\circ[/math]. Если точка [math]E[/math] не лежит в окружности, описанной вокруг треугольника [math]BDC[/math], то [math]\angle BEC \lt \angle BDC[/math], что противоречит предыдущим двум неравенствам. Очевидно, что угол [math]BED[/math] больше, чем угол [math]BEC[/math]. При этом точка [math]E[/math] лежит в окружности, описанной вокруг [math]BDC[/math]. Значит, при выборе треугольника нужно было взять не [math]ABC[/math], а [math]BDC[/math]. Противоречие.

[math]\triangleleft[/math]

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

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

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

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

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

Лемма (5):

Флип плохого ребра уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.

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

[math]\triangleright[/math]

Рассмотрим два таких смежных треугольника, что ребро между ними является плохим. Спроецируем их на параболоид. Четыре точки, принадлежащие смежным треугольникам, при проекции на параболоид образуют тетраэдр. Проведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит ниже этой плоскости (так как не выполняется локальный критерий Делоне), то есть тетраэдр лежит ниже тела, образующегося при проекции всей триангуляции на параболоид. После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.

[math]\triangleleft[/math]

Лемма (6):

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

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

[math]\triangleright[/math]

Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает (по лемме 5). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.

[math]\triangleleft[/math]

Лемма (7):

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

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

[math]\triangleright[/math]

Точка V вставлена в треугольник ABC Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро [math]VC[/math]. Проведём окружность, описывающую треугольник [math]ABC[/math]. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре [math]VC[/math] можно построить окружность, изнутри касающуюся окружность, описанную вокруг треугольника. В ней тоже нет никаких точек. Значит, для [math]VC[/math] выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой [math]V[/math], значит, оно хорошее. Случай, когда точка вставляется на ребро, рассматривается аналогично.

[math]\triangleleft[/math]

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

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

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

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

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

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

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

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

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

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

Бесконечно удалённая точка имеет координаты [math](0,0,1,0)[/math] (последняя координата — однородная).

Тогда проверка на то, является ли хорошим ребро, инцидентное бесконечно удалённой точке, упрощается: [math] \begin{vmatrix} a_x & a_y & a_x^2 + a_y^2 & 1 \\ b_x & b_y & b_y^2 + b_y^2 & 1 \\ c_x & c_y & c_x^2 + c_y^2 & 1 \\ 0 & 0 & 1 & 0 \end{vmatrix} = \begin{vmatrix} a_x & a_y & 1 \\ b_x & b_y & 1 \\ c_x & c_y & 1 \end{vmatrix} [/math], то есть достаточно проверить поворот трёх остальных точек образованного двумя бесконечными треугольниками четырёхугольника.

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

Время работы

Лемма (8):

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

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

[math]\triangleright[/math]

V — вставленная точка, ребро AC — плохое Доказательство по индукции. База. По лемме изначально не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точке. Переход. Рассмотрим, что произойдёт с противолежащим точке [math]V[/math] ребром [math]AC[/math] после флипа, если оно плохое. До вставки точки [math]V[/math] для триангуляции выполнялся глобальный критерий Делоне, поэтому в окружности, описанной вокруг треугольника [math]ACD[/math], не будет лежать никаких точек, кроме точки [math]V[/math]. Можно построить окружность, касающуюся её изнутри в точке [math]D[/math] и проходящую через точку [math]V[/math]. В ней тоже не окажется никаких точек, так как она касается изнутри. Значит, для ребра [math]VD[/math] выполняется критерий Делоне. Значит, после флипа ребро [math]AC[/math] уже не будет флипаться. Так как для рёбер [math]AV[/math] и [math]CV[/math] выполняется критерий Делоне, то плохими после флипа могут стать только рёбра [math]AD[/math] и [math]CD[/math] — то есть рёбра, противолежащие точке [math]V[/math].

[math]\triangleleft[/math]

Лемма (9):

Средняя степень вершины после вставки её в триангуляцию Делоне равна [math]O(1)[/math].

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

[math]\triangleright[/math]

Предположим, что мы вставляем [math]i+1[/math]-ую точку из последовательности из [math]n[/math] точек. Рассмотрим все перестановки из этих [math]i+1[/math] точек, означающие порядок вставки этих точек. Всего таких перестановок [math](i+1)![/math]. Тогда средняя степень последней вершины среди перестановок равна: [math]E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_1, v_2, ..., v_{i+1})} \operatorname{deg} (p[i+1])} {(i+1)!}[/math] Каждая из [math]i+1[/math] вершин побывает последней ровно [math]i![/math] раз, поэтому: [math]E(\operatorname{deg} (v_{i+1}))=\frac {\sum_{k=0}^{i} i! \operatorname{deg} (v_k)} {(i+1)!} = \frac {\sum_{k=0}^i \operatorname{deg}(v_k)} {i+1} = \frac {O(i+1)} {i+1} = O(1)[/math]

[math]\triangleleft[/math]

Теорема:

При вставке точки в триангуляцию Делоне в среднем придётся сделать [math]O(1)[/math] флипов.

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

[math]\triangleright[/math]

Все флипнутые рёбра окажутся инцидентными вставленной точке, а степень вершины — [math]O(1)[/math]. Поэтому будет сделано [math]O(1)[/math] флипов.

[math]\triangleleft[/math]

Так как среднее число флипов — [math]O(1)[/math], то время вставки целиком зависит от времени локализации.

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

Алгоритм

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

Время работы

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

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

Cтруктура

Локализационная структура состоит из нескольких уровней, где каждый уровень — это триангуляция Делоне. На нижнем уровне содержатся все точки. Каждая точка с вероятностью [math]p[/math] проходит на следующий уровень (причём если точка — единственная на последнем уровне, то дальше она не пройдёт).

Уровни связаны между собой следующим образом: на уровне [math]i[/math] каждая точка содержит указатель на себя же на уровне [math]i-1[/math].

Алгоритм локализации

Как происходит локализация: нам дают точку [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]

Ребро vv' должно принадлежать триангуляции Предположим, что это не так. Назовём локализуемую точку [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]\triangleleft[/math]

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

Память

Лемма (10):

Матожидание числа уровней в локализационной структуре — [math]O(\log n)[/math].

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

[math]\triangleright[/math]

Для оценки матожидания посчитаем вероятность того, что количество уровней [math]h[/math] равно [math]k[/math] при вероятности пройти на следующий уровень равной [math]p[/math]. [math]p(h \leq k) = (1 - p^{k + 1})^n[/math], потому что вероятность того, что точка дойдёт до уровня [math]k + 1[/math], равна [math]p^{k + 1}[/math]. [math]p(h \geq k) = (1 - (1 - p^k)^n)[/math], потому что вероятность того, что точка не дойдёт до уровня [math]k[/math], равна [math]1 - p^k[/math]. [math]p(h = k) = 1 - p(h \gt k) - p(h \lt k) = 1 - (1 - (1 - p^{k + 1})^n) - (1 - p^{k})^n = (1 - p^{k + 1})^n - (1 - p^k)^n \leq 1 - (1 - p^k)^n \leq np^k[/math] [math]E(h) = \sum\limits_{k = 1}^{\infty} k \cdot p(h = k) = p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n + \sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k)[/math] Оценим первую сумму: [math]p(1) \cdot 1 + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n \leq p(1) \cdot \log_{1/p} n + \dots + p(\log_{1/p} n) \cdot \log_{1/p} n = O(\log(n))[/math], поскольку сумма этих вероятностей не превосходит единицу. Оценим вторую сумму: [math]\sum\limits_{k = \log_{1/p} n + 1}^{\infty} k \cdot p(k) = \leq \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot n p^k = n \cdot \sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k[/math] Рассмотрим эту сумму: [math]\sum\limits_{k = \log_{1/p} n}^{\infty} k \cdot p^k = p^{\log_{1/p} n} \cdot \sum\limits_{k = 0}^{\infty} (k + \log_{1/p} n) \cdot p^k = p^{\log_{1/p} n} \cdot (\sum\limits_{k = 0}^{\infty} (k p^k) + \log_{1/p} n \cdot \sum\limits_{k = 0}^{\infty} (p^k)) = p^{\log_{1/p} n} \cdot (O(1) + \log_{1/p} n \cdot O(1)) = 1/n \cdot O(\log(n))[/math] Суммируя всё вышесказанное, получаем, что [math]O(\log(n))[/math].

[math]\triangleleft[/math]

Теорема:

Локализационная структура занимает [math]O(n)[/math] памяти.

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

[math]\triangleright[/math]

Триангуляция для [math]n[/math] точек занимает [math]O(n)[/math] памяти. На нулевом уровне [math]n[/math] точек. На уровне [math]k[/math] точек [math]m_k=p \cdot m_{k-1}[/math]. Получим геометрическую прогрессию, сумма которой равна [math]O(n)[/math].

[math]\triangleleft[/math]

Время работы

Лемма (11):

Каждая точка на плоскости может являться ближайшей для не более чем шести точек.

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

[math]\triangleright[/math]

Точка u является ближайшей для семи точек Предположим, что это не так. Пусть некоторая точка [math]u[/math] является ближайшей для семи точек. Соединим эти семь точек с точкой [math]u[/math] отрезками и рассмотрим минимальный из углов, который образуют проведённые отрезки [math]vu[/math] и [math]wu[/math]. Этот угол [math]\alpha[/math] меньше 60° (иначе все семь углов больше либо равны 60° и их сумма больше 360°). Так как точка [math]u[/math] ближайшая для точек [math]v[/math] и [math]w[/math], то [math]vw[/math] — наибольшая сторона в треугольнике [math]vwu[/math]. В треугольнике наибольшая сторона лежит напротив наибольшего угла. Но напротив стороны [math]vw[/math] лежит угол меньше 60°, значит, сумма углов треугольника меньше 180°. Противоречие. Значит, предположение неверно.

[math]\triangleleft[/math]

Лемма (12):

Для заданной точки [math]q[/math] на [math]k[/math]-ом уровне средняя степень ближайшей на [math]k+1[/math]-ом уровне вершины равна [math]O(1)[/math].

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

[math]\triangleright[/math]

Функция [math]nn[/math] принимает точку и множество и возвращает ближайшего соседа заданной точки из заданного множества. [math] \frac {1} {C^{|R_{k+1}|}_{|R_k|} |R_{k+1}|!} \cdot \sum_{R'_{k+1}\subset R_k} \operatorname{deg_{R_k}}(nn(R'_{k+1}[-1], R'_{k+1})) = [/math] TODO: А нужна ли нам эта строка? Рассмотрим некоторый уровень [math]S_k[/math]. Определим множество [math]R_k=S_k\cup\{q\}[/math]. Рассмотрим все возможные подмножества [math]R_k[/math], равномощные [math]R_{k+1}[/math], тем самым рассмотрев все возможные уровни [math]k+1[/math]. Для каждой точки из каждого подмножества [math]R'_{k+1}[/math] рассмотрим степень ближайшей вершины и усредним всё, получив нужную нам оценку. [math]E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \cdot \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i \in R'_{k+1}} \operatorname{deg_{R_k}} (\operatorname{nn}(a_i,R'_{k+1}\backslash\{a_i\})) [/math] Назовём графом [math]NN(\{a_i\})[/math] двудольный граф, в левой и правой долях содержащий точки [math]\{a_i\}[/math], рёбра [math]uv[/math] которого означают, что точка [math]v[/math] является ближайшей для точки [math]u[/math] (точка [math]u[/math] лежит в левой доли, точка [math]v[/math] лежит в правой доли). Понятно, что [math]\sum\limits_{a_i \in R'_{k+1}} \operatorname {deg_{R_k}} (\operatorname{nn}(a_i, R'_{k+1}\backslash\{a_i\})) = \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \cdot \operatorname{deg_{NN(R'_{k+1})}}(a_i)[/math], так как степень каждой вершины [math]a_i[/math] учтётся ровно столько раз, сколько рёбер ей инцидентно в правой доли графа [math]NN[/math]. [math]E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \operatorname{deg_{NN(R'_{k+1})}}(a_i)[/math] По лемме степень вершины из правой доли графа [math]NN[/math] не может быть больше шести. [math]E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) \le \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \cdot 6 = \frac {6} {C^{|R_{k+1}|}_{|R_k|} \cdot |R_{k+1}|} \sum\limits_{R'_{k+1}\subset R_k} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}} (a_i) = 6 \cdot \frac {\sum_{a_i\in R_k} \operatorname{deg}(a_i)} {|R_k|} = O(1) [/math]

[math]\triangleleft[/math]

Лемма (13):

Среднее число точек, лежащих в окружности с центром в точке [math]q[/math] и проходящей через [math]v_{i+1}[/math], равно [math]O(1)[/math].

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

[math]\triangleright[/math]

Докажем, что для заданной точки [math]w[/math] число таких точек [math]a[/math], что [math]w[/math] лежит в окружности с центром в точке [math]a[/math], проходящей через ближайшую к [math]a[/math] точку на предыдущем уровне, равно [math]O(1)[/math]. Разделим плоскость на шесть частей прямыми, проходящими через точку [math]w[/math] ( TODO: Почему именно на шесть?). Рассмотрим одну из частей. Отсортируем все точки, попавшие в неё, по увеличению расстояния до [math]w[/math]. Получим такую последовательность точек [math]\{a_0, a_1, ...\}[/math], что [math]|wa_i|\le|wa_{i+1}|[/math]. Заметим, что если какая-нибудь точка [math]a_i[/math] содержится на предыдущем уровне, то все точки, начиная с [math]a_{i+1}[/math] уже не содержат в своей окружности точку [math]w[/math]. Таким образом, среднее число точек [math]k[/math], в окружности которых содержится точка [math]w[/math]: [math]E(k)\le6\cdot\sum_i i(1-p)^i p = O(1)[/math] Таким образом, каждая точка содержится в [math]O(1)[/math] окружностей, значит, каждая окружность содержит [math]O(1)[/math] точек. TODO: А вот это я не очень понял

[math]\triangleleft[/math]

Лемма (14):

Среднее число рёбер, пересечённое отрезком [math]qv_{i+1}[/math] во втором этапе алгоритма локализации, равно [math]O(1)[/math].

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

[math]\triangleright[/math]

Рассмотрим рёбра, пересекающие [math]qv_{i+1}[/math], для которых хотя бы одна из граничных точек окажется в окружности с центром в точке [math]q[/math], проходящей через [math]v_{i+1}[/math]. Число таких рёбер не превосходит суммы степеней вершин, лежащих внутри окружности. А по лемме число таких точек равно [math]O(1)[/math]. При этом средняя степень вершины равна [math]O(1)[/math]. Таким образом, число таких рёбер равно [math]O(1)[/math]. Докажем, что число рёбер, пересекающих [math]qv_{i+1}[/math], для которых обе граничные точки лежат вне окружности, тоже равно [math]O(1)[/math]. При вставке точки [math]q[/math] в триангуляцию для этих рёбер перестанет выполняться критерий Делоне: в любой окружности, построенной на ребре как на хорде, будет содержаться либо точка [math]q[/math], либо точка [math]v_{i+1}[/math]. Поэтому эти рёбра придётся флипнуть. Число флипов при вставке точки равно [math]O(1)[/math], поэтому число таких рёбер равно [math]O(1)[/math]. Итого число рёбер, пересекающих [math]qv_{i+1}[/math], равно [math]O(1)[/math].

[math]\triangleleft[/math]

Лемма (15):

Среднее число треугольников, посещённых на третьем этапе алгоритма локализации, равно [math]O(1)[/math].

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

[math]\triangleright[/math]

Каждый рассмотренный треугольник имеет хотя бы одну вершину внутри окружности, проведённой через [math]v_{i+1}[/math], с центром в точке [math]q[/math]. То есть число таких треугольников не больше числа точек внутри этой окружности. Таких точек по лемме [math]O(1)[/math], значит, число треугольников тоже равно [math]O(1)[/math].

[math]\triangleleft[/math]

Лемма (16):

Локализация точки на каждом уровне происходит за [math]O(1)[/math].

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

[math]\triangleright[/math]

Докажем, что каждый этап локализации происходит за [math]O(1)[/math]. 1 этап: по лемме средняя степень вершины [math]v_{i+1}[/math] равна [math]O(1)[/math], поэтому треугольников, в которых может лежать отрезок [math]qv_{i+1}[/math] тоже [math]O(1)[/math]. Просмотрев их все, за [math]O(1)[/math] можно понять, в каком из них лежит отрезок [math]qv_{i+1}[/math]. 2 этап: число рёбер, пересечённых отрезком [math]qv_{i+1}[/math], равно [math]O(1)[/math] (по лемме). Поэтому этот этап локализации тоже происходит за [math]O(1)[/math]. 3 этап: число треугольников, посещённых на третьем этапе локализации, равно [math]O(1)[/math] (по лемме).

[math]\triangleleft[/math]

Теорема:

Локализация точки в триангуляции происходит за [math]O(\log n)[/math].

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

[math]\triangleright[/math]

Очевидное следствие из леммы о числе уровней и леммы о времени, требуемом на локализацию на каждом уровне.

[math]\triangleleft[/math]

Constraints

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

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

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

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

Вставка

Красным выделен вставляемый констрейнт

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

Удаление

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