212
правок
Изменения
Нет описания правки
===Принадлежность треугольнику===
Пусть дана даны точки <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> одинаковый.
===Алгоритм===
Пусть между плоскостями <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> и перейти к ней. Получили противоречие, значит алгоритм правильно находит ближайшую точку.
}}
{{Лемма
|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>E(X) \leqslant \sum\limits_{i = 1\dots\inf}{i \cdot p(1 - p) ^ i} = </tex>
<tex>\sum\limits_{i = 1\dots\inf}{\sum\limits_{j = i\dots\inf}{p (1 - p) ^ j}} = </tex>
<tex>p\sum\limits_{i = 1\dots\inf}{(1-p)^i \cdot (\sum\limits_{j = 0\dots\inf}{(1 - p) ^ j})} = \sum\limits_{i = 1\dots\inf}{(1-p)^i} = \frac{1-p}{p} = O(1)</tex>
Получается, что каждая точка принадлежит <tex>O(1)</tex>, следовательно внутри каждой окружности содержит <tex>O(1)</tex> точек.
}}
