Изменения
Нет описания правки
== Определение ==
{{Определение
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|proof=
Раскрывая скобки в уравнении окружности, получим <tex>(\vec O + \vec{r_i}, (\vec O + \vec{r_i})x^2) = (\vec O - 2ax + \vec{r_i}, \vec Oa^2 + \vec{r_i}y^2 - 2by + b^2\vec O \vec {r_i}) = (\vec O + \vec{r_i}, \vec Or^2 + R^2 + 2\vec O \vec {r_i})</tex>
Рассмотрим параболоид, пускай его уравнение имеет вид <tex>(\vec O + \vec{r_x}, (\vec O + \vec{r_x})^2) = (\vec O + \vec{r_x}, \vec Ox^2 + \vec{r_x}y^2 + 2\vec O \vec {r_x}) = (\vec O + \vec{r_x}, \vec O^2 + (tR)^2 + 2\vec O \vec {r_x})Cz</tex>.
Рассмотрим любую точку внутри данной окружности. Через нее можно провести окружность с центром в точке <tex>\begin{vmatrix}O (a, b)</tex> и радиусом <tex>r' < r</tex>, тогда плоскость, проходящая через проекцию этой окружности на параболоид будет иметь уравнение <tex>Ax + r_1 & OBy + Cz + D' = 0</tex>, то есть, обе плоскости будут параллельны и вторая плоскость будет лежать под плоскостью окружности (поскольку <tex>r' < r</tex>, то <tex>D' = (a^2 + Rb^2 + 2Or_1 & 1 \\\vdots & \vdots & \vdots \\O + r_{n+1} & O- r'^2 + R) > (a^2 + 2Or_{n+1} & 1 \\O + r_x & Ob^2 + (tR)- r^2 + 2Or_x & 1\end{vmatrix}) = 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) =