264
правки
Изменения
Нет описания правки
{{Лемма
|about=1
|id=1
|statement= Сечение сферы плоскостью есть окружность, а основание перпендикуляра, проведенного из центра шара к пересекаемой плоскости, есть центр окружности, полученной в сечении.
|proof=
{{Лемма
|about=2
|id=2
|statement= Гранями выпуклой оболочки будут выпуклые многоугольники
|proof=
{{Лемма
|about=6
|id=6
|statement=
Флипами можно достичь хорошей триангуляции за конечное время.
{{Лемма
|about=8
|id=8
|statement=
При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.
{{Лемма
|about=О степени вершины
|id=vertex_st
|statement=Математическое ожидание степени вершины после её вставки в триангуляцию Делоне равно <tex>O(1)</tex>.
|id=deglemma
{{Лемма
|about=9
|id=9
|statement=
Изначально нам будут видны грани, которые образуются внутри звездного многоугольника.
{{Лемма
|about=О количестве уровней
|id=10
|statement= Математическое ожидание уровней в локализационной структуре <tex> O(\log{n}) </tex>.
|proof= То же самое, что и для [[Триангуляция Делоне#levelslemma|плоскости]].
{{Лемма
|about=10
|id=111
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.
{{Лемма
|about=11
|id=212
|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>.
{{Лемма
|about=12
|id=313
|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне) равна <tex>O(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>.
{{Лемма
|id=4|statement=Точка на сфере может быть ближайшей для не более <tex>6</tex> точек.|proof=Пусть это не так. Тогда некоторая точка <tex>P</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем отрезки <tex>P A_i</tex>. Сумма углов между этими отрезками(дугами) равна <tex>2\pi</tex> Рассмотрим треугольник <tex>A_i P A_{i + 1}</tex>, где угол <tex>A_i P A_{i + 1}</tex> минимальный. Он строго меньше <tex>\dfrac{\pi}{3}</tex> (иначе сумма углов была бы больше <tex>2\pi</tex>). [https://lurklurk.com/Британские_учёные Британские ученые доказали], что сумма углов в сферическом треугольнике строго больше <tex>\pi</tex>(школьный факт).Однако по сферической теореме синусов напротив максимальной стороны лежит максимальный угол. Значит в таком треугольнике сумма углов меньше <tex>\pi<\tex>. Противоречие.}} {{Лемма|id=515
|statement=Степень ближайшей вершины <tex>O(1)</tex>
|proof=Доказательство копирует случай на [[Триангуляция Делоне#nearestdegreelemma|плоскости]].
{{Лемма
|id=616
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
|proof=По [[#2|лемме 11]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 12]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.
{{Лемма
|id=17
|statement=На втором этапе алгоритма луч в среднем пересечет <tex>O(1)</tex> ребер.
|proof=Рассмотрим окружность с центром в точке <tex>Q</tex>, проходящую через ближайшую для неё точку триангуляции <tex>P_{i + 1}</tex>.
|about=Следствие
|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>
|proof=
}}
{{Лемма
|id=18
|statement=Точка на сфере может быть ближайшей для не более <tex>6</tex> точек.
|proof=Пусть это не так. Тогда некоторая точка <tex>P</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем отрезки <tex>P A_i</tex>. Сумма углов между этими отрезками(дугами) равна <tex>2\pi</tex>
Рассмотрим треугольник <tex>A_i P A_{i + 1}</tex>, где угол <tex>A_i P A_{i + 1}</tex> минимальный. Он строго меньше <tex>\dfrac{\pi}{3}</tex> (иначе сумма углов была бы больше <tex>2\pi</tex>).
[[https://lurklurk.com/Британские_учёные |Британкие ученые доказали]}, что сумма углов в сферическом треугольнике строго больше <tex>\pi</tex>(школьный факт).
Однако по сферической теореме синусов напротив максимальной стороны лежит максимальный угол. Значит в таком треугольнике сумма углов меньше <tex>\pi</tex>. Противоречие.
}}
