1632
правки
Изменения
м
Докажем данное утверждение для n-мерного случая. Возьмём <tex>a_1, a_2, ..., a_{n+1}</tex> аффинно независимых точек и опишем вокруг них Рассмотрим окружность с центром в точке <tex>O</tex> и радиусом <tex>R</tex>. Возьмём произвольную точку <tex>x</tex>(a, лежащую на расстоянии <tex>tRb)</tex> от радиуса <tex>Or</tex>, и посмотрим, как параметр <tex>tона описывается уравнением: </tex> влияет на положение её проекции на параболоид. Представим <tex>\vec{a_i}</tex> как <tex>\vec O + \vec{r_i}</tex>, а <tex>\vec (x</tex> — как <tex>\vec O - a)^2 + \vec{r_x}(y - b)^2 = r^2</tex>. Тогда проекции точек на параболоид будут выглядеть так:
{{Acronym|Так как <tex>\{r_i\}</tex> аффинно независимыПри проецировании, для проекции окружности на параболоид верны оба уравнения: и окружности, и параболоида, то поэтому в уравнение окружности вместо <tex>r_xx^2 + y^2</tex> можно представить как подставить <tex>r_x = \sum_{i=1}^{n+1}\alpha_i r_iCz</tex>, причём получится <tex>\sum_{i=1}(-2a)x + (-2b)y + Cz + (a^{n2 +1}\alpha_i b^2 - r^2) = 10</tex>|Общеизвестный факт}}.
Запишем определительЗаметим, показывающий положение точки что получившееся уравнение является уравнением плоскости: <tex>xAx + By + Cz + D = 0</tex> на параболоиде относительно , то есть, все точки проекции окружности будут лежать в одной плоскости, заданной точками <tex>\{a_i\}</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> лежит ниже плоскости. Если же точка лежит на окружности, то она попадает на ту же плоскость.
rollbackEdits.php mass rollback
== Определение ==
{{Определение
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|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) =
