Изменения
Нет описания правки
== Определение ==
{{Определение
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|proof=
При проецировании, для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, поэтому в уравнение окружности вместо <tex>(\vec O x^2 + \vec{r_i}y^2</tex> можно подставить <tex>Cz</tex>, получится <tex>(\vec O -2a)x + \vec{r_i}(-2b)^2) = (\vec O y + \vec{r_i}, \vec O^2 Cz + \vec{r_i}(a^2 + 2\vec O \vec {r_i}) = (\vec O + \vec{r_i}, \vec Ob^2 + R- r^2 + 2\vec O \vec {r_i})= 0</tex>
Заметим, что получившееся уравнение является уравнением плоскости: <tex>(\vec O + \vec{r_x}, (\vec O + \vec{r_x})^2) = (\vec O Ax + \vec{r_x}, \vec O^2 By + \vec{r_x}^2 Cz + 2\vec O \vec {r_x}) D = (\vec O + \vec{r_x}, \vec O^2 + (tR)^2 + 2\vec O \vec {r_x})0</tex>, то есть, все точки проекции окружности будут лежать в одной плоскости.
}}
{{Теорема
== Локальный критерий Делоне ==
{{Определение
|definition='''Локальный критерий Делонедля ребра''': для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот).
}}
Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.
{{Определение
|definition=
}}
[[Файл:Flip.png|400px|thumb|right|Красное ребро — до флипа, синее — после]]
|proof=
[[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]
Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружностьокружности, описанную описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значитто есть, оно хорошее.
Случай, когда точка вставляется на ребро, рассматривается аналогично.
|proof=
[[Файл:Delaunay localization.png|400px|thumb|right|Ребро 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> удовлетворяет критерию Делоне и должно являться ребром триангуляции(по лемме 2), но по предположению этого ребра нет. Значит, предположение неверно.
}}
Оценим вторую сумму:
<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>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>.
}}
==== Время работы ====
{{Лемма
''Функция <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|}} \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) =
|id=diskvertexeslemma
|proof=
<tex>E(k)\le6\cdot\sum_i i(1-p)^i p = O(1)</tex>
Таким образом, каждая точка содержится в <tex>O(1)</tex> окружностей, значит, каждая окружность содержит <tex>O(1)</tex> точек. {{TODO|t=А вот это я не очень понял}}
}}
{{Лемма
|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>.
|id=triangleslemma
|proof=
Каждый рассмотренный треугольник имеет хотя бы одну вершину внутри окружности, проведённой через <tex>v_{i+1}</tex>, с центром в точке <tex>q</tex>. То есть число таких треугольников не больше числа точек внутри этой окружности. Таких точек [[#diskvertexeslemma|по лемме13]] <tex>O(1)</tex>, значит, число треугольников тоже равно <tex>O(1)</tex>.
}}
{{Лемма
Докажем, что каждый этап локализации происходит за <tex>O(1)</tex>.
'''1 этап''': [[#nearestdegreelemma|по лемме12]] средняя степень вершины <tex>v_{i+1}</tex> равна <tex>O(1)</tex>, поэтому треугольников, в которых может лежать отрезок <tex>qv_{i+1}</tex> тоже <tex>O(1)</tex>. Просмотрев их все, за <tex>O(1)</tex> можно понять, в каком из них лежит отрезок <tex>qv_{i+1}</tex>.
'''2 этап''': число рёбер, пересечённых отрезком <tex>qv_{i+1}</tex>, равно <tex>O(1)</tex> ([[#edgeslemma|по лемме14]]). Поэтому этот этап локализации тоже происходит за <tex>O(1)</tex>.
'''3 этап''': число треугольников, посещённых на третьем этапе локализации, равно <tex>O(1)</tex> ([[#triangleslemma|по лемме15]]).
}}
{{Теорема
Локализация точки в триангуляции происходит за <tex>O(\log n)</tex>.
|proof=
Очевидное следствие из [[#levelslemma|леммы о числе уровней10]] и [[#onelevellemma|леммы о времени, требуемом на локализацию на каждом уровне16]].
}}