355
правок
Изменения
м
Нет описания правки
== Существование триангуляции Делоне ==
{{Лемма
|about=1
|statement=
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
}}
{{Лемма
|about=2
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
|proof=
Будем называть '''хорошими''' те рёбра, для которых выполняется локальный критерий Делоне.
{{Лемма
|about=3
|id=fliplemma
|statement=
}}
{{Лемма
|about=4
|statement=
Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоне.
Из [[#fliplemma|леммы]] следует, что если ребро плохое, то флип сделает его хорошим.
{{Лемма
|about=5
|statement=Флип плохого ребра уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
|id=volumelemma
}}
{{Лемма
|about=6
|statement=
Флипами можно достичь хорошей триангуляции за конечное время.
}}
{{Лемма
|about=7
|statement=
Если в триангуляцию Делоне вставить точку в некоторый треугольник и соединить его вершины с этой точкой, то получившиеся рёбра будут хорошими.
==== Время работы ====
{{Лемма
|about=8
|statement=
При вставке точки будут флипаться только рёбра, противолежащие вставленной точке.
}}
{{Лемма
|about=9
|statement=
Средняя степень вершины после вставки её в триангуляцию Делоне равна <tex>O(1)</tex>.
==== Память ====
{{Лемма
|about=10
|statement=
Матожидание числа уровней в локализационной структуре — <tex>O(\log n)</tex>.
==== Время работы ====
{{Лемма
|about=11
|statement=Каждая точка на плоскости может являться ближайшей для не более чем шести точек.
|id=closestlemma
}}
{{Лемма
|about=12
|statement=Для заданной точки <tex>q</tex> на <tex>k</tex>-ом уровне средняя степень ближайшей на <tex>k+1</tex>-ом уровне вершины равна <tex>O(1)</tex>.
|id=nearestdegreelemma
}}
{{Лемма
|about=13
|statement=Среднее число точек, лежащих в окружности с центром в точке <tex>q</tex> и проходящей через <tex>v_{i+1}</tex>, равно <tex>O(1)</tex>.
|id=diskvertexeslemma
}}
{{Лемма
|about=14
|statement=Среднее число рёбер, пересечённое отрезком <tex>qv_{i+1}</tex> во втором этапе алгоритма локализации, равно <tex>O(1)</tex>.
|id=edgeslemma
}}
{{Лемма
|about=15
|statement=Среднее число треугольников, посещённых на третьем этапе алгоритма локализации, равно <tex>O(1)</tex>.
|id=triangleslemma
}}
{{Лемма
|about=16
|statement=
Локализация точки на каждом уровне происходит за <tex>O(1)</tex>.
