Изменения

Перейти к: навигация, поиск

Триангуляция Делоне на сфере

8 байт добавлено, 12:21, 29 ноября 2016
Алгоритм
{{Лемма
|about=13
|id=4
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
|proof=По [[#2|лемме 11]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 12]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.
}}
 
{{Лемма
|statement=Точка на сфере может быть ближайшей для не более <tex>6</tex> точек.
|proof=Пусть это не так. Тогда некоторая точка <tex>P</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем отрезки <tex>O P A_i</tex>. Получили семигранный угол. По свойствам многогранных углов: сумма их плоских Сумма углов не превосходит <tex>360</tex>. Проведем <tex>7</tex> полуплоскостей с основанием между этими отрезками(дугами) равна <tex>OP2\pi</tex>, каждая из которых содержит соответствующий отрезок <tex>O A_i</tex>.
Плоский угол Рассмотрим треугольник <tex>A_i O P A_{i + 1}</tex> не меньше угла между полуплоскостями, содержащими отрезки где угол <tex>O A_iP A_{i + 1}</tex> и минимальный. Он строго меньше <tex>O A_\dfrac{\pi}{i + 13}</tex>. Тогда так как (иначе сумма углов между полуплоскостями равна была бы больше <tex>3602\pi</tex>, получаем). [https://lurklurk.com/Британские_учёные Британские ученые доказали], что сумма плоских углов в семигранном угле не менее сферическом треугольнике строго больше <tex>360\pi</tex>(школьный факт).Однако по сферической теореме синусов напротив максимальной стороны лежит максимальный угол. Значит в таком треугольнике сумма углов меньше <tex>\pi<\tex>. Противоречие, значит такого быть не может.
}}
{{Лемма
|id=5
|statement=Степень ближайшей вершины <tex>O(1)</tex>
|proof=Доказательство копирует случай на [[Триангуляция Делоне#nearestdegreelemma|плоскости]].
}}
 
{{Лемма
|id=6
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
|proof=По [[#2|лемме 11]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 12]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.
}}
 
{{Лемма
Анонимный участник

Навигация