212
правок
Изменения
→Локализация в триангуляции
|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>U</tex> является ближайшей для <tex>7</tex> точек: <tex>A_1 \dots A_7</tex>. Проведем плоскости вида <tex>UO A_i</tex>. Угол мнежду этими плоскостями строго меньше <tex>60</tex> градусов (иначе сумма углов превосходила бы <tex>360</tex>).
Рассмотрим плоскость <tex> A_i U A_{i + 1} </tex>. Угол <tex> A_i U A_{i + 1} </tex> равен углу между плоскостями <tex>UOA_i</tex> и <tex>UOA_{i + 1}</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>.
Осталось посчитать ребра, границы которых не лежат внутри окружности. При вставке точки <tex>Q</tex> в триангуляцию для таких ребер испортится критерий Делоне, так как внутри любой окружности построенной на этом ребре будет либо точка <tex>Q</tex>, либо точка <tex>P_{i + 1}</tex>. Значит, что эти ребра надо будет флипнуть, а так как при вставке в среднем флипается <tex>O(1)</tex> ребер, то луч пересечет <tex>O(1)</tex> ребер.
}}
|about=Следствие
|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>
}}
====Движение вдоль луча====
Когда нам надо пройти по триангуляции вдоль какого-то луча <tex>PQ</tex>, то ,оказавшись в каком-то треугольнике, надо проверить, что точка <tex>Q</tex> принадележит этому треугольнику. Если принадлежит, то мы останавливаем свой обход, иначе находим какую сторону пересекал луч и переходим в смежный этой стороне треугольник.
{{Теорема
|statement=Луч <tex>PQ</tex> пересекает отрезок <tex>AB</tex> тогда и только тогда, когда повороты точек <tex>A</tex> и <tex>B</tex> относительно <tex>PQ</tex> различены, а повороты <tex>B</tex> и <tex>Q</tex> относительно <tex>AP</tex> совпадают.
|proof='''Необходимость'''
<tex>AB</tex> пересекает <tex>PQ</tex>. Очевидно, что в этом случае повороты точек <tex>A</tex> и <tex>B</tex> относительно <tex>PQ</tex> различены. Рассмотрим повороты <tex>B</tex> и <tex>Q</tex> относительно <tex>AP</tex>. Если они различны, тогда луч <tex>PQ</tex> и отрезок <tex>AB</tex> лежат в разных полусферах, но они пересекаются, значит такого быть не может и повороты должны совпадать.
'''Достаточность'''
Предикат выполняется. Значит отрезок <tex>AB</tex> пересекает прямую <tex>PQ</tex>. Луч <tex>PQ</tex> в свою очередь есть половина прямой <tex>PQ</tex>. Из того, что повороты <tex>B</tex> и <tex>Q</tex> относительно <tex>AP</tex> совпадают, следует, что отрезок <tex>AB</tex> находится в одной полусфере с лучем <tex>PQ</tex>, значит они пересекаются.
}}
