Изменения
Нет описания правки
== Определение ==
{{Определение
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|proof=
Рассмотрим окружность с центром в точке <tex>(a, b)</tex> и радиуса <tex>r</tex>, она описывается уравнением: <tex>(x - a)^2 + (y - b)^2 = r^2</tex>.
Рассмотрим параболоид, пускай его уравнение имеет вид <tex>x^2 + y^2 = Cz</tex>.
При проецировании, для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, поэтому в уравнение окружности вместо <tex>x^2 + y^2</tex> можно подставить <tex>Cz</tex>, получится <tex>(-2a)x + (-2b)y + Cz + (a^2 + b^2 - r^2) = 0</tex>
Заметим, что получившееся уравнение является уравнением плоскости: <tex>Ax + By + Cz + D = 0</tex>, то есть, все точки проекции окружности будут лежать в одной плоскости.
Рассмотрим любую точку внутри данной окружности. Через нее можно привести провести окружность с центром в точке <tex>(a, b)</tex> и радиусом <tex>r' < r</tex>, тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь формулу уравнение <tex>Ax + 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>).
Аналогично доказывается, что точки лежащие вне окружности лежат над плоскостью.
== Локальный критерий Делоне ==
{{Определение
|definition='''Локальный критерий Делонедля ребра''': для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот).
}}
Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.
|proof=
[[Файл:Good edge.png|400px|thumb|right|Точка V вставлена в треугольник ABC]]
Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</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>.
}}
==== Время работы ====
{{Лемма
<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|лемме 1211]] степень вершины из правой доли графа <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) =
