3
правки
Изменения
Лемма о степени вершины
===Вставка точки===
{{Лемма
|about=О степени вершины
|statement=Математическое ожидание степени вершины после её вставки в триангуляцию Делоне равна <tex>O(1)</tex>.
|id=deglemma
|proof=
Предположим, что мы вставляем <tex>i+1</tex>-ую точку из последовательности из <tex>n</tex> точек. Рассмотрим все перестановки из этих <tex>i+1</tex> точек, означающие порядок вставки этих точек. Всего таких перестановок <tex>(i+1)!</tex>. Тогда средняя степень последней вершины среди перестановок равна:
<tex>E(\operatorname{deg}(v_{i+1}))=\frac {\sum_{p=perm(v_0, v_1, ..., v_i)} \operatorname{deg} (p[i+1])} {(i+1)!}</tex>
Каждая из <tex>i+1</tex> вершин побывает последней ровно <tex>i!</tex> раз, поэтому:
<tex>E(\operatorname{deg} (v_{i+1}))=\frac {\sum_{k=0}^{i} i! \operatorname{deg} (v_k)} {(i+1)!} = \frac {\sum_{k=0}^i \operatorname{deg}(v_k)} {i+1}</tex>
По лемме о рукопожатиях <tex>\sum_{k=0}^{i} \operatorname{deg}(v_k) = 2D</tex>, где <tex>D</tex> - количество ребер. Следовательно: <tex>E(\operatorname{deg} (v_{i+1}))=\frac {2D} {i+1}</tex>
Триангуляция Делоне на сфере является планарным графом на сфере, чья укладка эквивалентна укладке на плоскости (см. сфера Римана). Значит, для неё справедлива формула Эйлера: <tex>V-D+F=2</tex>, где <tex>V</tex> - количество вершин, а <tex>F</tex> - количество граней. Так как каждая грань образована тремя рёбрами, и при этом при подсчёте каждое ребро учитывается дважды, имеем: <tex>3F=2D=>F=\frac {2D} {3}</tex>. Подставив в формулу Эйлера, получим:
<tex>V-D+\frac {2D} {3}=2=>\frac {1} {3}D=V-2=>D=3(V-2)=3((i+1)-2)=3(i-1)</tex>
В итоге <tex>E(\operatorname{deg} (v_{i+1}))=\frac {2D} {i+1}=\frac {6(i-1)} {i+1}=O(1)</tex>.
}}
===Удаление точки===
===Локализация в триангуляции===
