355
правок
Изменения
м
→Время работы
<tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) = \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \operatorname{deg_{NN(R'_{k+1})}}(a_i)</tex>
По [[#closestlemma|лемме12]] степень вершины из правой доли графа <tex>NN</tex> не может быть больше шести.
<tex>E(\operatorname{deg_{S_k}} (\operatorname{nn} (q, S_{k+1}))) \le \frac {1} {C^{|R_{k+1}|}_{|R_k|}} \sum\limits_{R'_{k+1}\subset R_k} \frac {1} {|R_{k+1}|} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}}(a_i) \cdot 6 = \frac {6} {C^{|R_{k+1}|}_{|R_k|} \cdot |R_{k+1}|} \sum\limits_{R'_{k+1}\subset R_k} \sum\limits_{a_i\in R'_{k+1}} \operatorname{deg_{R_k}} (a_i) =
|id=edgeslemma
|proof=
Рассмотрим рёбра, пересекающие <tex>qv_{i+1}</tex>, для которых хотя бы одна из граничных точек окажется в окружности с центром в точке <tex>q</tex>, проходящей через <tex>v_{i+1}</tex>. Число таких рёбер не превосходит суммы степеней вершин, лежащих внутри окружности. А [[#diskvertexeslemma|по лемме13]] число таких точек равно <tex>O(1)</tex>. При этом средняя степень вершины равна <tex>O(1)</tex>. Таким образом, число таких рёбер равно <tex>O(1)</tex>.
Докажем, что число рёбер, пересекающих <tex>qv_{i+1}</tex>, для которых обе граничные точки лежат вне окружности, тоже равно <tex>O(1)</tex>. При вставке точки <tex>q</tex> в триангуляцию для этих рёбер перестанет выполняться критерий Делоне: в любой окружности, построенной на ребре как на хорде, будет содержаться либо точка <tex>q</tex>, либо точка <tex>v_{i+1}</tex>. Поэтому эти рёбра придётся флипнуть. Число флипов при вставке точки [[#flipnumberlemma|равно <tex>O(1)</tex>]], поэтому число таких рёбер равно <tex>O(1)</tex>.
|id=triangleslemma
|proof=
Каждый рассмотренный треугольник имеет хотя бы одну вершину внутри окружности, проведённой через <tex>v_{i+1}</tex>, с центром в точке <tex>q</tex>. То есть число таких треугольников не больше числа точек внутри этой окружности. Таких точек [[#diskvertexeslemma|по лемме13]] <tex>O(1)</tex>, значит, число треугольников тоже равно <tex>O(1)</tex>.
}}
{{Лемма
Докажем, что каждый этап локализации происходит за <tex>O(1)</tex>.
'''1 этап''': [[#nearestdegreelemma|по лемме12]] средняя степень вершины <tex>v_{i+1}</tex> равна <tex>O(1)</tex>, поэтому треугольников, в которых может лежать отрезок <tex>qv_{i+1}</tex> тоже <tex>O(1)</tex>. Просмотрев их все, за <tex>O(1)</tex> можно понять, в каком из них лежит отрезок <tex>qv_{i+1}</tex>.
'''2 этап''': число рёбер, пересечённых отрезком <tex>qv_{i+1}</tex>, равно <tex>O(1)</tex> ([[#edgeslemma|по лемме14]]). Поэтому этот этап локализации тоже происходит за <tex>O(1)</tex>.
'''3 этап''': число треугольников, посещённых на третьем этапе локализации, равно <tex>O(1)</tex> ([[#triangleslemma|по лемме15]]).
}}
{{Теорема
Локализация точки в триангуляции происходит за <tex>O(\log n)</tex>.
|proof=
Очевидное следствие из [[#levelslemma|леммы о числе уровней10]] и [[#onelevellemma|леммы о времени, требуемом на локализацию на каждом уровне16]].
}}
