355
правок
Изменения
→Время работы
}}
==== Время работы ====
{{Лемма
|statement=Среднее число точек, лежащих в окружности с центром в точке <tex>q</tex> и проходящей через <tex>v_{i+1}</tex>, равно <tex>O(1)</tex>.
|id=diskvertexeslemma
|proof=
{{TODO|t=Proof}}
}}
{{Лемма
|statement=Среднее число рёбер, пересечённое отрезком <tex>qv_{i+1}</tex> во втором этапе алгоритма локализации, равно <tex>O(1)</tex>.
|id=edgeslemma
|proof=
Для каждого ребра, пересекающего <tex>qv_{i+1}</tex>, хотя бы одна из его точек окажется в окружности с центром в точке <tex>q</tex>, проходящей через <tex>v_{i+1}</tex>. {{TODO|t=ДоказательствоПочему?}}Поэтому число рёбер не превосходит суммы степеней вершин, лежащих внутри окружности. А [[#diskvertexeslemma|по лемме]] число таких точек равно <tex>O(1)</tex>. При этом средняя степень вершины равна <tex>O(1)</tex>. Таким образом, число пересечённых рёбер равно <tex>O(1)</tex>.
}}
{{Лемма
|id=triangleslemma
|proof=
Каждый рассмотренный треугольник имеет хотя бы одну вершину внутри окружности, проведённой через <tex>v_{{TODOi+1}</tex>, с центром в точке <tex>q</tex>. То есть число таких треугольников не больше числа точек внутри этой окружности. Таких точек [[#diskvertexeslemma|t=Доказательство}}по лемме]] <tex>O(1)</tex>, значит, число треугольников тоже равно <tex>O(1)</tex>.
}}
{{Лемма
