355
правок
Изменения
→Время работы, требуемая память
|statement=
Матожидание числа уровней в локализационной структуре — <tex>O(\log n)</tex>.
|id=levelslemma
|proof=
Для оценки матожидания посчитаем вероятность того, что количество уровней <tex>h</tex> равно <tex>k</tex> при вероятности пройти на следующий уровень равной <tex>p</tex>.
|statement=
Локализация точки на каждом уровне происходит за <tex>O(1)</tex>.
|id=onelevellemma
|proof=
Докажем, что каждый этап локализации происходит за <tex>O(1)</tex>. '''1 этап''': средняя степень вершины <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> {{TODO|t=Почему?}}. Поэтому этот этап локализации тоже происходит за <tex>O(1)</tex>. '''3 этап''': число треугольников, посещённых на третьем этапе локализации, равно <tex>O(1)</tex> {{TODO|t=ДоказательствоПочему?}}.
}}
{{Теорема
Локализация точки в триангуляции происходит за <tex>O(\log n)</tex>.
|proof=
Очевидное следствие из двух предыдущих лемм[[#levelslemma|леммы о числе уровней]] и [[#onelevellemma|леммы о времени, требуемом на локализацию на каждом уровне]].
}}
{{Теорема
