2
правки
Изменения
м
{{ptready}}
{{TODO|t=Перенумеровать леммы}}
Докажем данное утверждение для nРассмотрим окружность с центром в точке <tex>(a, b)</tex> радиуса <tex>r</tex>, она описывается уравнением: <tex>(x -мерного случаяa)^2 + (y - b)^2 = r^2</tex>.
Возьмём <tex>a_1Раскрывая скобки в уравнении окружности, a_2, ..., a_{n+1}</tex> аффинно независимых точек и опишем вокруг них окружность с центром в точке <tex>O</tex> и радиусом <tex>R</tex>. Возьмём произвольную точку получим <tex>x^2 - 2ax + a^2 + y^2 - 2by + b^2 = r^2</tex>, лежащую на расстоянии <tex>tR</tex> от <tex>O</tex>, и посмотрим, как параметр <tex>t</tex> влияет на положение её проекции на параболоид.
Представим <tex>\vec{a_i}</tex> как <tex>\vec O + \vec{r_i}</tex>Рассмотрим параболоид, а пускай его уравнение имеет вид <tex>\vec x</tex> — как <tex>\vec O ^2 + \vec{r_x}y^2 = Cz</tex>. Тогда проекции точек на параболоид будут выглядеть так:
{{Acronym|Так как Рассмотрим любую точку внутри данной окружности. Через нее можно провести окружность с центром в точке <tex>\{r_i\}(a, b)</tex> аффинно независимыи радиусом <tex>r' < r</tex>, тогда плоскость, то проходящая через проекцию этой окружности на параболоид будет иметь уравнение <tex>r_xAx + By + Cz + D' = 0</tex> можно представить как , то есть, обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r_x = \sum_{i=1}^{n+1}\alpha_i r_ir' < r</tex>, причём то <tex>\sum_{iD' =1}(a^2 + b^2 - r'^2) > (a^{n2 +1}\alpha_i b^2 - r^2) = 1D</tex>|Общеизвестный факт}}).
Запишем определительАналогично доказывается, показывающий положение что точки <tex>x</tex> на параболоиде относительно плоскости, заданной точками <tex>\{a_i\}</tex>:лежащие вне окружности лежат над плоскостью.
<tex>
\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}
</tex>
Умножим первые <tex>n+1</tex> строк на <tex>\alpha_i</tex> и вычтем из последней:
<tex>
\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}
</tex>
Из определителя видно, что знак определителя зависит от ориентации исходных точек <tex>\{a_i\}</tex> и от знака <tex>t^2-1</tex>. Для определённости будем считать, что точки <tex>\{a_i\}</tex> ориентированы так, что предикат поворота положителен. Тогда если <tex>t > 1</tex> (точка <tex>x</tex> лежит вне окружности), то определитель положителен, то есть точка <tex>x</tex> лежит выше плоскости, заданной точками <tex>\{a_i\}</tex>. Если же <tex>t < 1</tex> (точка <tex>x</tex> лежит внутри окружности), то определитель отрицателен, и точка <tex>x</tex> лежит ниже плоскости. Если же точка лежит на окружности, то она попадает на ту же плоскость.
Для пары Рассмотрим пару смежных треугольников . Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется '''flip''' — убирание смежного ребра и проведение другого('''флип''').
<tex> \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})) = </tex>
{{TODO|t=А нужна ли нам эта строка?}}
Докажем, что для заданной Рассмотрим точки триангуляции <tex>w\{a_i\}</tex> число таких точек <tex>a. Для каждой точки </tex>, что <tex>wa_i</tex> лежит в окружности построим окружность с центром в точке <tex>aa_i</tex>, проходящей проходящую через ближайшую к ней точку. Докажем, что заданная точка <tex>aw</tex> точку на предыдущем уровне, равно попадёт в <tex>O(1)</tex>таких окружностей на предыдущем уровне. Разделим плоскость на шесть частей прямыми, проходящими через точку <tex>w</tex> ({{TODO|t=Почему именно на шесть?}}). Рассмотрим одну из частей. Отсортируем все точки, попавшие в неё, по увеличению расстояния до <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>:
Исправлена опечатка
{{nohate}}
== Определение ==
{{Определение
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|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=
Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#volumelemma|по лемме5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.
}}
{{Лемма
|proof=
[[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]
Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружностьокружности, описанную описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значитто есть, оно хорошее.
Случай, когда точка вставляется на ребро, рассматривается аналогично.
Если же точка лежит на ребре, два смежных с ребром фейса превращаем в два новых, добавляем ещё два, а так же превращаем ребро, на которое вставляется точка, в ребро, которое заканчивается в этой точке, и вставляем три новых.
Итого у нас появилось несколько новых рёбер. Они все хорошие (по [[#newedgeslemma|лемме7]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.
==== Вставка точки, лежащей снаружи триангуляции ====
Доказательство по индукции.
База. По [[#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>.
|id=flipnumberlemma
|proof=
Все флипнутые рёбра окажутся инцидентными вставленной точке(по лемме 8), а [[#deglemma|степень вершины — <tex>O(1)</tex>(по лемме 9)]]. Поэтому будет сделано <tex>O(1)</tex> флипов.
}}
Так как среднее число флипов — <tex>O(1)</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]].
}}
