Изменения

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

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

Докажем данное утверждение для n-мерного случая. Возьмём <tex>a_1, a_2, ..., a_{n+1}</tex> афинно независимых точек и опишем вокруг них Рассмотрим окружность с центром в точке <tex>O</tex> и радиусом <tex>R</tex>. Возьмём произвольную точку <tex>x</tex>(a, лежащую на расстоянии <tex>tR</tex> от <tex>O</tex>, и посмотрим, как параметр <tex>t</tex> влияет на положение её проекции на параболоид. Представим <tex>\vec{a_i}b)</tex> как радиуса <tex>\vec O + \vec{r_i}r</tex>, а <tex>\vec x</tex> — как <tex>\vec O + \vec{r_x}</tex>. Тогда проекции точек на параболоид будут выглядеть такона описывается уравнением: <tex>(\vec O + \vec{r_i}, (\vec O + \vec{r_i}x - a)^2+ (y - b) = (\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 + Rr^2 + 2\vec O \vec {r_i})</tex>.

Раскрывая скобки в уравнении окружности, получим <tex>(\vec O + \vec{r_x}, (\vec O + \vec{r_x})x^2) = (\vec O - 2ax + \vec{r_x}, \vec Oa^2 + \vec{r_x}y^2 - 2by + b^2\vec O \vec {r_x}) = (\vec O + \vec{r_x}, \vec Or^2 + (tR)^2 + 2\vec O \vec {r_x})</tex>

Так как <tex>\{r_i\}</tex> афинно независимыРассмотрим параболоид, то <tex>r_xпускай его уравнение имеет вид </tex> можно представить как <tex>r_x = \sum_{i=1}x^{n2 +1}\alpha_i r_i</tex>, причём <tex>\sum_{i=1}y^{n+1}\alpha_i 2 = 1Cz</tex>.

Запишем определительПри проецировании, показывающий положение точки для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, поэтому в уравнение окружности вместо <tex>x^2 + y^2</tex> можно подставить <tex>Cz</tex> на параболоиде относительно плоскости, заданной точками получится <tex>\{a_i\}(-2a)x + (-2b)y + Cz + (a^2 + b^2 - r^2) = 0</tex>:

Заметим, что получившееся уравнение является уравнением плоскости: <tex>\begin{vmatrix}O Ax + r_1 & O^2 By + R^2 Cz + 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}D = 0</tex>, то есть, все точки проекции окружности будут лежать в одной плоскости.

Умножим первые Рассмотрим любую точку внутри данной окружности. Через нее можно провести окружность с центром в точке <tex>n+1(a, b)</tex> и радиусом <tex>r' < r</tex> строк , тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь уравнение <tex>\alpha_iAx + By + Cz + D' = 0</tex> , то есть, обе плоскости будут параллельны и вычтем из последней:вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r' < r</tex>, то <tex>D' = (a^2 + b^2 - r'^2) > (a^2 + b^2 - r^2) = D</tex>).

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

 == Динамическая триангуляция Локальный критерий Делоне ==

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

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

Ну предположим[[Файл:Bad triangle.png|400px|thumb|right|Все рёбра треугольника хорошие, но описанная окружность содержит точки]]Предположим, что это не так, то есть все рёбра хорошие, но существует треугольниксуществуют треугольники, описанная окружность которого содержит которых содержат какие-либо точки триангуляции. Тогда очевидноВозьмём какую-либо конфликтную точку <tex>E</tex>. Рассмотрим такой треугольник <tex>ABC</tex> из тех, в описанную окружность которых попадает <tex>E</tex>, что угол <tex>BEC</tex> максимален, если <tex>BC</tex> — ближайшая к точке <tex>E</tex> сторона. Пусть треугольник <tex>BDC</tex> — смежный с <tex>ABC</tex>. Докажем, что точка <tex>E</tex> лежит в окружности, описанной вокруг <tex>BDC</tex>. Предположим, что одно из рёбер этого это не так. Посмотрим на окружность, описанную вокруг треугольника окажется плохим<tex>ABC</tex>: <tex>\angle BAC + \angle BEC > 180^\circ</tex> и <tex>\angle BAC + \angle BDC < 180^\circ</tex>. ПротиворечиеЕсли точка <tex>E</tex> не лежит в окружности, описанной вокруг треугольника <tex>BDC</tex>, то <tex>\angle BEC < \angle BDC</tex>, что противоречит предыдущим двум неравенствам.{{TODO|t=ДоказатьОчевидно, что угол <tex>BED</tex> больше, чем угол <tex>BEC</tex>. При этом точка<tex>E</tex> лежит в окружности, лежащая внутри окружностиописанной вокруг <tex>BDC</tex>. Значит, при выборе треугольника нужно было взять не <tex>ABC</tex>, будет принадлежать смежному треугольнику}}а <tex>BDC</tex>. Противоречие.

Для пары Рассмотрим пару смежных треугольников . Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется '''flip''' — убирание смежного ребра и проведение другого('''флип''').

[[Файл:FlipПроведём через какой-нибудь из двух треугольников плоскость.png|400px|thumb|right|Красное ребро — до флипаВершина, синее — после]]противолежащая основанию тетраэдра, являющегося этим треугольником, лежит ниже этой плоскости (так как не выполняется локальный критерий Делоне), то есть тетраэдр лежит ниже тела, образующегося при проекции всей триангуляции на параболоид.

Из После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.}}{{Лемма|about=6|statement=Флипами можно достичь хорошей триангуляции за конечное время.|proof=Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#fliplemmavolumelemma|леммыпо лемме 5]] следует). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, что если ребро плохоетребуемых для достижения триангуляции Делоне, то флип сделает его хорошимтоже конечно.}}

Очевидно[[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]Предположим, потому что каждый флип уменьшает разность объёмов параболоида и точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, то есть, оно хорошее. Случай, спроецированной когда точка вставляется на негоребро, рассматривается аналогично.

Итого у нас появилось несколько новых рёбер. Они все хорошие ({{TODOпо [[#newedgeslemma|t=Доказать, почему}}лемме 7]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей. Среднее число флипов — <tex>O(1)</tex> ({{TODO|t=Доказать, почему}}). Поэтому время вставки целиком зависит от времени локализации.

Бесконечно удалённая точка имеет координаты <tex>(0,0,1,0)</tex> (последняя координата — однородная). Тогда проверка на то, является ли хорошим ребро, инцидентное бесконечно удалённой точке, упрощается:<tex>\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}</tex>, то есть достаточно проверить поворот трёх остальных точек образованного двумя бесконечными треугольниками четырёхугольника. Проверка, принадлежит ли точка бесконечному треугольнику, тоже проста: нужно, чтобы из точки было видно ребро, противолежащее бесконечно удалённой точке, в бесконечном треугольнике. Это проверяется предикатом поворота. ==== Время работы ===={{TODOЛемма|tabout=Написать про бесконечно удалённую 8|statement=При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.|proof=[[Файл:Flip edges.png|400px|thumb|right|V — вставленная точка, ребро AC — плохое]]Доказательство по индукции. База. По [[#newedgeslemma|лемме 7]] изначально не будут флипаться новые рёбра, инцидентные точке, то есть плохими могут оказаться только рёбра, противолежащие точке. Переход. Рассмотрим, что произойдёт с противолежащим точке <tex>V</tex> ребром <tex>AC</tex> после флипа, если оно плохое. До вставки точки <tex>V</tex> для триангуляции выполнялся глобальный критерий Делоне, поэтому в окружности, описанной вокруг треугольника <tex>ACD</tex>, не будет лежать никаких точек, кроме точки <tex>V</tex>. Можно построить окружность, касающуюся её изнутри в точке <tex>D</tex> и проходящую через точку <tex>V</tex>. В ней тоже не окажется никаких точек, так как она касается изнутри. Значит, для ребра <tex>VD</tex> выполняется критерий Делоне. Значит, после флипа ребро <tex>AC</tex> уже не будет флипаться. Так как для рёбер <tex>AV</tex> и <tex>CV</tex> выполняется критерий Делоне, то плохими после флипа могут стать только рёбра <tex>AD</tex> и <tex>CD</tex> — то есть рёбра, противолежащие точке <tex>V</tex>.}}{{Лемма|about=9|statement=Средняя степень вершины после вставки её в триангуляцию Делоне равна <tex>O(1)</tex>.|id=deglemma|proof=Предположим, что мы вставляем <tex>i+1</tex>-ую точкуиз последовательности из <tex>n</tex> точек. Рассмотрим все перестановки из этих <tex>i+1</tex> точек, означающие порядок вставки этих точек. Всего таких перестановок <tex>(i+1)!</tex>. Тогда средняя степень последней вершины среди перестановок равна: <tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_1, v_2, ..., v_{i+1})} \operatorname{deg} (p[i+1])} {(i+1)!}</tex> Каждая из <tex>i+1</tex> вершин побывает последней ровно <tex>i!</tex> раз, поэтому: <tex>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)</tex>}}{{Теорема|statement=При вставке точки в триангуляцию Делоне в среднем придётся сделать <tex>O(1)</tex> флипов.|id=flipnumberlemma|proof=Все флипнутые рёбра окажутся инцидентными вставленной точке (по лемме 8), а [[#deglemma|степень вершины — <tex>O(1)</tex> (по лемме 9)]]. Поэтому будет сделано <tex>O(1)</tex> флипов.}}Так как среднее число флипов — <tex>O(1)</tex>, то время вставки целиком зависит от времени локализации.

==== Алгоритм ====При удалении точки получится {{Acronym|звёздный многоугольник, который можно затриангулировать за линию|Почему на эту тему нет конспекта? Я не собираюсь тут это доказыватьОбщеизвестный факт}}. Дальше При этом все рёбра, полученные в результате триангуляции звёздного многоугольника, могут оказаться плохими, поэтому необходимо пройтись по традиции флипаем всёним и пофлипать, что могло стать плохимесли нужно.==== Время работы ===={{Acronym|Средняя степень вершины в триангуляции — <tex>O(1)</tex>|Общеизвестный факт}}, поэтому триангуляция звёздного многоугольника будет тоже за <tex>O(1)</tex>. Новых рёбер получится <tex>O(1)</tex>, пока не получим хорошую триангуляциюпроверить их на локальный критерий Делоне и пофлипать тоже можно за <tex>O(1)</tex>. Итого удаление точки работает за <tex>O(1)</tex>.

Средняя степень вершины в триангуляции — <tex>O(1)</tex> ({{TODO|t=Почему?}} — почти то, что нужно, здесь [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0_%D0%B4%D0%B5%D1%82%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%82%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D0%B8#.D0.92.D1.8B.D0.B1.D0.BE.D1.80_.D0.BC.D0.BD.D0.BE.D0.B6.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D1.83.D0.B4.D0.B0.D0.BB.D1.8F.D0.B5.D0.BC.D1.8B.D1.85_.D0.B2.D0.B5.D1.80.D1.88.D0.B8.D0.BD]. Потом пишем <tex>\sum_{v \in V}{deg(v)} Локализационная структура ===== Cтруктура = 2E</tex>, делим на <tex>|V|</tex> и получаем <tex>avg(deg(v)) = \frac{O(|V|)}{|V|} = O(1)</tex>)Локализационная структура состоит из нескольких уровней, поэтому где каждый уровень — это триангуляция звёздного многоугольника будет тоже за Делоне. На нижнем уровне содержатся все точки. Каждая точка с вероятностью <tex>O(1)p</tex>. С флипами всё тожепроходит на следующий уровень (причём если точка — единственная на последнем уровне, в общем-то, хорошо. Итого удаление точки работает за <tex>O(1дальше она не пройдёт)</tex>.

== Локализационная структура ===== Сама структура ===В общем-то, довольно стандартная схема для рандомизированных структурУровни связаны между собой следующим образом: на нижнем уровне содержатся все точки; <tex>i</tex> каждая точка с вероятностью p проходит содержит указатель на себя же на следующий уровеньуровне <tex>i-1</tex>.=== Локализация Алгоритм локализации ===

{{TODO[[Файл:Delaunay localization.png|400px|thumb|right|t=Картинку для ясности}}Ребро vv' должно принадлежать триангуляции]]Предположим, что это не так. Назовём локализуемую точку <tex>q</tex>, а последнего кандидата на то, чтобы быть ближайшей точкой — <tex>v</tex>. Раз эта точка на самом деле не ближайшая, то в окружности, проходящей через <tex>v</tex>, с центром в точке <tex>q</tex> найдутся ещё какие-то точки, не смежные с <tex>v</tex>. Рассмотрим ближайшую Проведём через каждую из них к окружность, касающуюся изнутри в точке <tex>v</tex>: изначальную окружность. Рассмотрим точку <tex>v'</tex>. Построим на <tex>vv'</tex> , через которую проходит наименьшая окружность как на диаметреиз построенных. В этой окружности не будет лежать никаких точек, так как мы взяли ближайшуюнаименьшую. Значит, ребро <tex>vv'</tex> удовлетворяет критерию Делоне и должно являться ребром триангуляции(по лемме 2), но по предположению этого ребра нет. Значит, предположение неверно.}} === Время работы, требуемая память ======= Память ===={{Лемма|about=10|statement=Матожидание числа уровней в локализационной структуре — <tex>O(\log n)</tex>.|id=levelslemma|proof=Для оценки матожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex> при вероятности пройти на следующий уровень равной <tex>p</tex>. <tex>p(h \leq k) = (1 - p^{k + 1})^n</tex>, потому что вероятность того, что точка дойдёт до уровня <tex>k + 1</tex>, равна <tex>p^{k + 1}</tex>. <tex>p(h \geq k) = (1 - (1 - p^k)^n)</tex>, потому что вероятность того, что точка не дойдёт до уровня <tex>k</tex>, равна <tex>1 - p^k</tex>. <tex>p(h = k) = 1 - p(h > k) - p(h < 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</tex> <tex>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)</tex> Оценим первую сумму: <tex>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))</tex>, поскольку сумма этих вероятностей не превосходит единицу. Оценим вторую сумму: <tex>\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</tex> Рассмотрим эту сумму: <tex>\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))</tex> Суммируя всё вышесказанное, получаем, что <tex>O(\log(n))</tex>.}}{{Теорема|statement=Локализационная структура занимает <tex>O(n)</tex> памяти.|proof=Триангуляция для <tex>n</tex> точек занимает <tex>O(n)</tex> памяти. На нулевом уровне <tex>n</tex> точек. На уровне <tex>k</tex> точек <tex>m_k=p \cdot m_{k-1}</tex>. Получим геометрическую прогрессию, сумма которой равна <tex>O(n)</tex>.}} ==== Время работы ===={{Лемма|about=11|statement=Каждая точка на плоскости может являться ближайшей для не более чем шести точек.|id=closestlemma|proof=[[Файл:Closest deg.png|400px|thumb|right|Точка ''u'' является ближайшей для семи точек]] Предположим, что это не так. Пусть некоторая точка <tex>u</tex> является ближайшей для семи точек. Соединим эти семь точек с точкой <tex>u</tex> отрезками и рассмотрим минимальный из углов, который образуют проведённые отрезки <tex>vu</tex> и <tex>wu</tex>. Этот угол <tex>\alpha</tex> меньше 60° (иначе все семь углов больше либо равны 60° и их сумма больше 360°). Так как точка <tex>u</tex> ближайшая для точек <tex>v</tex> и <tex>w</tex>, то <tex>vw</tex> — наибольшая сторона в треугольнике <tex>vwu</tex>. В треугольнике наибольшая сторона лежит напротив наибольшего угла. Но напротив стороны <tex>vw</tex> лежит угол меньше 60°, значит, сумма углов треугольника меньше 180°. Противоречие. Значит, предположение неверно.}}{{Лемма|about=12|statement=Для заданной точки <tex>q</tex> на <tex>k</tex>-ом уровне средняя степень ближайшей на <tex>k+1</tex>-ом уровне вершины равна <tex>O(1)</tex>.|id=nearestdegreelemma|proof= ''Функция <tex>nn</tex> принимает точку и множество и возвращает ближайшего соседа заданной точки из заданного множества.'' Рассмотрим некоторый уровень <tex>S_k</tex>. Определим множество <tex>R_k=S_k\cup\{q\}</tex>. Рассмотрим все возможные подмножества <tex>R_k</tex>, равномощные <tex>R_{k+1}</tex>, тем самым рассмотрев все возможные уровни <tex>k+1</tex>. Для каждой точки из каждого подмножества <tex>R'_{k+1}</tex> рассмотрим степень ближайшей вершины и усредним всё, получив нужную нам оценку. <tex>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\})) </tex> Назовём графом <tex>NN(\{a_i\})</tex> двудольный граф, в левой и правой долях содержащий точки <tex>\{a_i\}</tex>, рёбра <tex>uv</tex> которого означают, что точка <tex>v</tex> является ближайшей для точки <tex>u</tex> (точка <tex>u</tex> лежит в левой доли, точка <tex>v</tex> лежит в правой доли). Понятно, что <tex>\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)</tex>, так как степень каждой вершины <tex>a_i</tex> учтётся ровно столько раз, сколько рёбер ей инцидентно в правой доли графа <tex>NN</tex>. <tex>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)</tex> По [[#closestlemma|лемме 11]] степень вершины из правой доли графа <tex>NN</tex> не может быть больше шести. <tex>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)</tex>}}{{Лемма|about=13|statement=Среднее число точек, лежащих в окружности с центром в точке <tex>q</tex> и проходящей через <tex>v_{i+1}</tex>, равно <tex>O(1)</tex>.|id=diskvertexeslemma|proof=Рассмотрим точки триангуляции <tex>\{a_i\}</tex>. Для каждой точки <tex>a_i</tex> построим окружность с центром в точке <tex>a_i</tex>, проходящую через ближайшую к ней точку. Докажем, что заданная точка <tex>w</tex> попадёт в <tex>O(1)</tex> таких окружностей на предыдущем уровне. Разделим плоскость на шесть частей прямыми, проходящими через точку <tex>w</tex>. Рассмотрим одну из частей. Отсортируем все точки, попавшие в неё, по увеличению расстояния до <tex>w</tex>. Получим такую последовательность точек <tex>\{a_0, a_1, ...\}</tex>, что <tex>|wa_i|\le|wa_{i+1}|</tex>. Заметим, что если какая-нибудь точка <tex>a_i</tex> содержится на предыдущем уровне, то все точки, начиная с <tex>a_{i+1}</tex> уже не содержат в своей окружности точку <tex>w</tex>. Таким образом, среднее число точек <tex>k</tex>, в окружности которых содержится точка <tex>w</tex>: <tex>E(k)\le6\cdot\sum_i i(1-p)^i p = O(1)</tex> Таким образом, каждая точка содержится в <tex>O(1)</tex> окружностей, значит, каждая окружность содержит <tex>O(1)</tex> точек.}}{{Лемма|about=14|statement=Среднее число рёбер, пересечённое отрезком <tex>qv_{i+1}</tex> во втором этапе алгоритма локализации, равно <tex>O(1)</tex>.|id=edgeslemma|proof=Рассмотрим рёбра, пересекающие <tex>qv_{i+1}</tex>, для которых хотя бы одна из граничных точек окажется в окружности с центром в точке <tex>q</tex>, проходящей через <tex>v_{i+1}</tex>. Число таких рёбер не превосходит суммы степеней вершин, лежащих внутри окружности. А [[#diskvertexeslemma|по лемме 13]] число таких точек равно <tex>O(1)</tex>. При этом средняя степень вершины равна <tex>O(1)</tex>. Таким образом, число таких рёбер равно <tex>O(1)</tex>. Докажем, что число рёбер, пересекающих <tex>qv_{i+1}</tex>, для которых обе граничные точки лежат вне окружности, тоже равно <tex>O(1)</tex>. При вставке точки <tex>q</tex> в триангуляцию для этих рёбер перестанет выполняться критерий Делоне: в любой окружности, построенной на ребре как на хорде, будет содержаться либо точка <tex>q</tex>, либо точка <tex>v_{i+1}</tex>. Поэтому эти рёбра придётся флипнуть. Число флипов при вставке точки [[#flipnumberlemma|равно <tex>O(1)</tex>]], поэтому число таких рёбер равно <tex>O(1)</tex>. Итого число рёбер, пересекающих <tex>qv_{i+1}</tex>, равно <tex>O(1)</tex>.}}{{Лемма|about=15|statement=Среднее число треугольников, посещённых на третьем этапе алгоритма локализации, равно <tex>O(1)</tex>.|id=triangleslemma|proof=Каждый рассмотренный треугольник имеет хотя бы одну вершину внутри окружности, проведённой через <tex>v_{i+1}</tex>, с центром в точке <tex>q</tex>. То есть число таких треугольников не больше числа точек внутри этой окружности. Таких точек [[#diskvertexeslemma|по лемме 13]] <tex>O(1)</tex>, значит, число треугольников тоже равно <tex>O(1)</tex>.

=== Профит ==='''3 этап''': число треугольников, посещённых на третьем этапе локализации, равно <tex>O(1)</tex> ([[#triangleslemma|по лемме 15]]).}}{{TODOТеорема|statement=Локализация точки в триангуляции происходит за <tex>O(\log n)</tex>.|tproof=Время работы, требуемая памятьОчевидное следствие из [[#levelslemma|леммы 10]] и [[#onelevellemma|леммы 16]].}}

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

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

[[Файл:Constraint.png|400px|thumb|right|Красным выделен вставляемый констрейнт]]Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом ({{TODO|t=Картинку бы}}), и флипаем их. Последнее флипнутое ребро и будет констрейнтом {{Acronym|(по понятным причинам)|Рёбра, пересечённые констрейнтом, после флипа будут начинаться в той же точке, что и констрейнт, а заканчиваться в точке, в которой начинается ещё одно пересекающее ребро. Последнее же ребро будет начинаться и заканчиваться в начале и конце констрейнта}}, после флипа пометим его как констрейнт. Понятное дело, критерий «хорошести» ребра при таких фокусах немного изменится: туда добавится проверка на то, не является ли ребро констрейнтом. Затем флипаем всё, что могло стать плохим (кроме констрейнта), пока триангуляция вновь не станет условно хорошей. {{TODO|t=Тут должно быть ещё несколько упоительных фактов про то, что вставка производится за <tex>O(k^2)</tex>, где <tex>k</tex> — число пересечённых рёбер, и про то, что, если флипать что попало, можно нарваться на флип в невыпуклом многоугольнике}} 

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