Изменения

Пусть дана даны точки <tex>P</tex>, <tex>A</tex>, <tex>B</tex>, <tex>C</tex> на сфере с центром <tex>O</tex>, тогда <tex>P</tex> принадлежит треугольнику <tex>ABC</tex>, тогда и только тогда, когда поворот <tex>P</tex> относительно плоскостей <tex>AOB</tex>, <tex>BOC</tex>, <tex>COA</tex> одинаковый.

|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки.То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции. Проведем в точке <tex>P</tex> касательную плоскость <tex>\beta</tex> к сфере. Очевидно, что она делит всё пространство на <tex>2</tex> части: в первой нет никаких точек, а во второй находятся все точки триангуляции.Пусть между плоскостями <tex>\alpha</tex> и <tex>\beta</tex> угол <tex>\gamma</tex>. Начнем его уменьшать, то есть поворачивать плоскость <tex>\beta</tex>. Очевидно, что она начнет пересекать сферу, тогда она будет соответствовать какой-то окружности на сфере. При этом все точки сферы, которые выше плоскости <tex>\beta</tex> будут выше плоскости <tex>\alpha</tex>, значит это будет вложенная окружность.Будем уменьшать угол <tex>\gamma</tex> до того момента, когда какая-то точка <tex>P'</tex>, лежащая внутри окружности(такая есть по предположению), не станет принадлежать плоскости <tex>\beta</tex>. В этот момент выше плоскости <tex>\beta</tex> нет ни одной точки из триангуляции. Значит для ребра <tex>PP'</tex> можно провести окружность, не содержащую других точек, то есть выполняется глобальный критерий Делоне. Значит в триангуляции должно быть ребро <tex>PP'</tex>, и по алгоритму мы должны были его перебрать и увидеть, что <tex>P'</tex> ближе к точке <tex>Q</tex> и перейти к ней. Получили противоречие, значит алгоритм правильно находит ближайшую точку.}} {{Лемма|about=2|id=2|statement=Среднее число точек, лежащих внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>V_{i + 1}</tex> равно <tex>O(1)</tex>.|proof=Рассмотрим точки триангуляции <tex>\{A_i\}</tex>. Для каждой точки <tex> A_i</tex> проведем окружность с центром в ней, проходящую через ближайшую к ней точку. Посчитаем во сколько окружностей в среднем попадет точка какая-то точка <tex>U</tex>. Проведем через <tex>OU</tex> три плоскости так, чтобы они делили всё пространство на <tex>6</tex> равных частей. Покажем, что в одной части <tex>O(1)</tex> окружностей будут включать в себя точку <tex>U</tex>, тогда всего таких окружностей будет тоже <tex>O(1)</tex>.Рассмотрим одну часть. Отсортируем точки, которые ей принадлежат, по степени удаленности от точки <tex>U</tex>. Окрасим точки в два цвета:* красный {{---}} точки с <tex>i</tex> уровня* черный {{---}} точки с <tex>i + 1</tex> уровняЕсли на <tex>j</tex>-ой позиции находится черная точка, то точки с индексом <tex>j + 1</tex> и далее не будут содержать в окружности точку <tex>U</tex>(потому что <tex>j</tex> была ближайшей на предыдущем уровне из этой части пространства). Тогда если <tex> X </tex> {{---}} количество окружностей, которым принадлежит точка <tex>U</tex>, то так как точка проходит на следующий уровень с вероятностью <tex>p</tex>: <tex dpi = 150>E(X) \leqslant \sum\limits_{i = 1\dots\infty}{i \cdot p(1 - p) ^ i} = </tex><tex dpi = 150>\sum\limits_{i = 1\dots\infty}{\sum\limits_{j = i\dots\infty}{p (1 - p) ^ j}} = </tex><tex dpi = 150>p\sum\limits_{i = 1\dots\infty}{(1-p)^i \cdot (\sum\limits_{j = 0\dots\infty}{(1 - p) ^ j})} = \sum\limits_{i = 1\dots\infty}{(1-p)^i} = \frac{1-p}{p} = O(1)</tex>Получается, что каждая точка принадлежит <tex>O(1)</tex>, следовательно внутри каждой окружности содержит <tex>O(1)</tex> точек.}} {{Лемма|about=3|id=3|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне)|proof=Пусть есть функция <tex>circle(q, p, i)</tex>, возвращающая <tex>1</tex>, если точка <tex>p</tex> принадлежит окружности с центром в точке <tex>q</tex>, проходящую через ближайшую к <tex>q</tex> на <tex>i</tex> уровне точку, а иначе <tex>0</tex>. Пусть <tex>Points_i</tex> {{---}} множество точек на <tex>i</tex>-ом уровне.<tex>X</tex> {{---}} степень вершины внутри окружности, тогда: <tex dpi = 130>E(X) = \dfrac{\sum\limits_{q \in Points_{i - 1}}{\sum\limits_{p \in Points_{i - 1}}{circle(q, p, i) \cdot deg(p)}}}{\left| Points_{i - 1} \right|} =</tex> Меняем порядок суммирования, и получаем: <tex dpi = 130>= \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{q \in Points_{i - 1}}{circle(q, p, i)}}}{\left| Points_{i - 1} \right|} \leqslant</tex> По предыдущей лемме получаем: <tex dpi = 130>\leqslant \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{1 \dots \infty}{i \cdot p \cdot (1 - p) ^ i}}}{\left| Points_{i - 1} \right|} \approx</tex> <tex dpi = 130>\approx \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \dfrac{O(n)}{n} = O(1)</tex>}} {{Лемма|about=4|id=4|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>|proof=По [[#2|лемме 2]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 3]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.}} {{Теорема|about=Следствие|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>