355
правок
Изменения
м
→Время работы
}}
==== Время работы ====
{{Лемма
|statement=Для заданной точки <tex>q</tex> на <tex>k</tex>-ом уровне средняя степень ближайшей на <tex>k+1</tex>-ом уровне вершины равна <tex>O(1)</tex>.
|id=nearestdegreelemma
|proof={{TODO|t=proof}}
}}
{{Лемма
|statement=Среднее число точек, лежащих в окружности с центром в точке <tex>q</tex> и проходящей через <tex>v_{i+1}</tex>, равно <tex>O(1)</tex>.
Докажем, что каждый этап локализации происходит за <tex>O(1)</tex>.
'''1 этап''': [[#nearestdegreelemma|по лемме]] средняя степень вершины <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|по лемме]]). Поэтому этот этап локализации тоже происходит за <tex>O(1)</tex>.
