212
правок
Изменения
Нет описания правки
Если на <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> точек.
}}
{{Лемма
|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 = 150>E(X) = \frac{\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 = 150>= \frac{\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 = 150>\leqslant \frac{\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 = 150>\approx \frac{\sum\limits_{p \in Points_{i - 1}}{deg(p)}}{\left| Points_{i - 1} \right|} = \frac{O(n)}{n} = O(1)</tex>
}}
