212
правок
Изменения
Нет описания правки
{{Лемма
|about=1
|id=1
|statement=Алгоритм найдет ближайшую точку
|proof=Допустим, что это не так. Это значит, что в внутри окружности с центром в точке <tex>Q</tex>, на которой лежит точка <tex>P</tex>, есть какие-то другие точки. То есть другими словами существует плоскость <tex>\alpha</tex> проходящая через точку <tex>P</tex>, выше которой находятся точка <tex>Q</tex>(так как она центр) и какие-то точки триангуляции.
{{Лемма
|about=2
|id=2
|statement=Среднее число точек, лежащих внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>V_{i + 1}</tex> равно <tex>O(1)</tex>.
|proof=Рассмотрим точки триангуляции <tex>\{A_i\}</tex>. Для каждой точки <tex> A_i</tex> проведем окружность с центром в ней, проходящую через ближайшую к ней точку. Посчитаем во сколько окружностей в среднем попадет точка какая-то точка <tex>U</tex>.
Если на <tex>j</tex>-ой позиции находится черная точка, то точки с индексом <tex>j + 1</tex> и далее не будут содержать в окружности точку <tex>U</tex>(потому что <tex>j</tex> была ближайшей на предыдущем уровне из этой части пространства). Тогда если <tex> X </tex> {{---}} количество окружностей, которым принадлежит точка <tex>U</tex>, то так как точка проходит на следующий уровень с вероятностью <tex>p</tex>:
<texdpi = 150>E(X) \leqslant \sum\limits_{i = 1\dots\infinfty}{i \cdot p(1 - p) ^ i} = </tex><texdpi = 150>\sum\limits_{i = 1\dots\infinfty}{\sum\limits_{j = i\dots\infinfty}{p (1 - p) ^ j}} = </tex><texdpi = 150>p\sum\limits_{i = 1\dots\infinfty}{(1-p)^i \cdot (\sum\limits_{j = 0\dots\infinfty}{(1 - p) ^ j})} = \sum\limits_{i = 1\dots\infinfty}{(1-p)^i} = \frac{1-p}{p} = O(1)</tex>
Получается, что каждая точка принадлежит <tex>O(1)</tex>, следовательно внутри каждой окружности содержит <tex>O(1)</tex> точек.
}}
{{Лемма
|about=3
|id=3
|statement=Средняя степень точек на <tex>i</tex> уровне внутри окружности с центром в точке <tex>Q</tex> и проходящей через точку <tex>P_{i + 1}</tex>(ближайшая точка на <tex>i + 1</tex> уровне)
|proof=Пусть есть функция <tex>circle(q, p, i)</tex>, возвращающая <tex>1</tex>, если точка <tex>p</tex> принадлежит окружности с центром в точке <tex>q</tex>, проходящую через ближайшую к <tex>q</tex> на <tex>i</tex> уровне точку, а иначе <tex>0</tex>.
Пусть <tex>Points_i</tex> {{---}} множество точек на <tex>i</tex>-ом уровне.
<tex>X</tex> {{---}} степень вершины внутри окружности, тогда:
<tex dpi = 130>E(X) = \dfrac{\sum\limits_{q \in Points_{i - 1}}{\sum\limits_{p \in Points_{i - 1}}{circle(q, p, i) \cdot deg(p)}}}{\left| Points_{i - 1} \right|} =</tex>
Меняем порядок суммирования, и получаем:
<tex dpi = 130>= \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{q \in Points_{i - 1}}{circle(q, p, i)}}}{\left| Points_{i - 1} \right|} \leqslant</tex>
По предыдущей лемме получаем:
<tex dpi = 130>\leqslant \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p) \sum\limits_{1 \dots \infty}{i \cdot p \cdot (1 - p) ^ i}}}{\left| Points_{i - 1} \right|} \approx</tex>
<tex dpi = 130>\approx \dfrac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \dfrac{O(n)}{n} = O(1)</tex>
}}
{{Лемма
|about=4
|id=4
|statement=Один уровень в среднем обрабатывается за <tex>O(1)</tex>
|proof=По [[#2|лемме 2]] алгоритм пройдет в среднем <tex>O(1)</tex> вершин, степень которых так же равна по [[#3|лемме 3]] <tex>O(1)</tex>, следовательно один уровень будет обработан за <tex>O(1)</tex>.
}}
{{Теорема
|about=Следствие
|statement=Локализация в среднем работает за <tex>O(\log{n})</tex>
}}
