212
правок
Изменения
→Алгоритм
{{Лемма
|statement=Точка на сфере может быть ближайшей для не более <tex>6</tex> точек.
|proof=Пусть это не так. Тогда некоторая точка <tex>UP</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем плоскости вида отрезки <tex>UO O A_i</tex>. Угол мнежду этими плоскостями строго меньше Получили семигранный угол. По свойствам многогранных углов: сумма их плоских углов не превосходит <tex>360</tex>. Проведем <tex>7</tex> полуплоскостей с основанием <tex>60OP</tex> градусов (иначе сумма углов превосходила бы , каждая из которых содержит соответствующий отрезок <tex>360O A_i</tex>). Рассмотрим плоскость Плоский угол <tex> A_i U O A_{i + 1} </tex>. Угол не меньше угла между полуплоскостями, содержащими отрезки <tex> O A_i U </tex> и <tex>O A_{i + 1} </tex> равен углу . Тогда так как сумма углов между плоскостями полуплоскостями равна <tex>UOA_i360</tex> и , получаем, что сумма плоских углов в семигранном угле не менее <tex>UOA_{i + 1}360</tex>(следовательно он меньше 60 градусов). Противоречие, аналогично для других углов треугольниказначит такого быть не может.
}}
{{Лемма
|statement=Степень ближайшей вершины <tex>O(1)</tex>
|proof=TBDДоказательство копирует случай на плоскости.
}}
{{Лемма
|statement=На третьем втором этапе алгоритма луч в среднем пересечет <tex>O(1)</tex> ребер.
|proof=Рассмотрим окружность с центром в точке <tex>Q</tex>, проходящую через ближайшую для неё точку триангуляции <tex>P_{i + 1}</tex>.
Количество таких ребер, хотя бы одна граница которых принадлежит окружности не превосходит суммы степеней вершин внутри окружности, следовательно их <tex>O(1)</tex>.
