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''' — убирание смежного ребра и проведение другого('''флип''').
Очевидное следствие из Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#volumelemma|леммыпо лемме 5]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.
{{TODO|t=Как сделан переход от степеней вершин к O-шкам?}}
Докажем, что для заданной Рассмотрим точки триангуляции <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}}
== Определение ==
{{Определение
== Существование триангуляции Делоне ==
{{Лемма
|about=1
|statement=
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|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>, то есть, все точки проекции окружности будут лежать в одной плоскости.
}}
{{Теорема
Все грани выпуклой оболочки окажутся внутри параболоида из-за его выпуклости. При этом точки лежат на параболоиде. Поэтому не найдётся точек, которые будут лежать за гранями выпуклой оболочки. То есть все точки, спроецированные на параболоид, будут принадлежать выпуклой оболочке.
По лемме 1 очевидно, что внутри окружностей, описанных вокруг проекций граней выпуклой оболочки, не будет лежать никаких точек. Значит, проекции граней — фигуры подразбиения Делоне. Значит, такое подразбиение существует.
Из единственности выпуклой оболочки следует, что такое подразбиение единственно.
}}
{{Лемма
|about=2
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
|proof=
== Локальный критерий Делоне ==
{{Определение
|definition='''Локальный критерий Делонедля ребра''': для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот).
}}
Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.
{{Лемма
|about=3
|id=fliplemma
|statement=
}}
{{Лемма
|about=4
|statement=
Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоне.
{{Определение
|definition=
}}
[[Файл:Flip.png|400px|thumb|right|Красное ребро — до флипа, синее — после]]
Из [[#fliplemma|леммы3]] следует, что если ребро плохое, то флип сделает его хорошим.
{{Лемма
|about=5
|statement=Флип плохого ребра уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
|id=volumelemma
}}
{{Лемма
|about=6
|statement=
Флипами можно достичь хорошей триангуляции за конечное время.
|proof=
}}
{{Лемма
|about=7
|statement=
Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.
|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]]), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.
==== Вставка точки, лежащей снаружи триангуляции ====
==== Время работы ====
{{Лемма
|about=8
|statement=
При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.
Доказательство по индукции.
База. По [[#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>.
<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>
}}
{{Теорема
|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), но по предположению этого ребра нет. Значит, предположение неверно.
}}
==== Память ====
{{Лемма
|about=10
|statement=
Матожидание числа уровней в локализационной структуре — <tex>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>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'_{TODOk+1})}}(a_i)</tex> По [[#closestlemma|tлемме 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) =proof6 \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>E(k)\le6\cdot\sum_i i(1-p)^i p = O(1)</tex>
Таким образом, каждая точка содержится в <tex>O(1)</tex> окружностей, значит, каждая окружность содержит <tex>O(1)</tex> точек. {{TODO|t=А вот это я не очень понял}}
}}
{{Лемма
|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>.
}}
{{Лемма
|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>.
}}
{{Лемма
|about=16
|statement=
Локализация точки на каждом уровне происходит за <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]].
}}
