Триангуляция Делоне

2014-02-10T19:42:48Z

193.107.90.37: /* Удаление точки */

{{ptready}}
{{nohate}}
== Определение ==
{{Определение
|definition=
'''Подразбиение Делоне''' — такое разбиение плоскости на множество выпуклых фигур, что в окружности, описанной вокруг любой из фигур, не находится никаких точек.
}}
{{Определение
|definition=
'''Триангуляция Делоне''' — триангуляция, являющаяся подразбиением Делоне.
}}

== Существование триангуляции Делоне ==
{{Лемма
|statement=
Окружность, спроецированная на параболоид, находится в одной плоскости. Все точки, лежащие внутри окружности, будут лежать под этой плоскостью. Точки, лежащие вне окружности, будут лежать над плоскостью.
|proof=
{{TODO|t=Тут будет какой-то определитель спроецированных на параболоид точек}}
<tex>
\begin{vmatrix}
x & y \\
z & v
\end{vmatrix}
</tex>
}}
{{Теорема
|statement=
Подразбиение Делоне существует, причём для каждого набора точек оно единственно.
|proof=
Спроецируем все точки на параболоид и построим выпуклую оболочку. По лемме очевидно, что внутри окружностей, описанных вокруг проекций граней выпуклой оболочки, не будет лежать никаких точек. Значит, проекции граней — фигуры подразбиения Делоне. Значит, такое подразбиение существует.

Из единственности выпуклой оболочки следует, что такое подразбиение единственно.
}}

== Некоторые упоительные факты ==
{{TODO|t=Раскидать это всё в те разделы, где это нужно}}
{{Определение
|definition='''Критерий Делоне для ребра''' — на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.
}}
{{Лемма
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне
|proof=
{{TODO|t=А как это вообще доказывается?}}
}}
{{Определение
|definition=Ребро назовём '''хорошим''', если для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот)
}}
{{Лемма
|statement=
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее
|proof=
Спроецируем четыре точки на параболоид. Очевидно, что по ним можно построить четырёхугольник {{Acronym|двумя способами: в первом случае он будет «вогнутым», во втором — «выпуклым»|Если все четыре точки лежат на одной окружности, то оба ребра будут хорошими, так как четырёхугольник можно будет построить только один}}. По доказанному выше факту про окружность, спроецированную на параболоид, выпуклое ребро будет хорошим.
}}
{{Лемма
|statement=
Если все рёбра хорошие, то и триангуляция хорошая
|proof=
Ну предположим, что это не так, то есть все рёбра хорошие, но существует треугольник, описанная окружность которого содержит какие-либо точки триангуляции. Тогда очевидно, что одно из рёбер этого треугольника окажется плохим. Противоречие.
}}
{{Определение
|definition=
Для пары смежных треугольников '''flip''' — убирание смежного ребра и проведение другого
}}
Из первой леммы следует, что, если ребро плохое, то флип сделает его хорошим.
{{Лемма
|statement=
Флипами можно достичь хорошей триангуляции за конечное время
|proof=
Очевидно, потому что каждый флип уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
}}

== Динамическая триангуляция ==
=== Вставка точки ===
==== Вставка точки, лежащей внутри триангуляции ====
{{TODO|t=Надо бы вставить сюда картинки}}

Для начала локализуемся: поймём, в каком фейсе лежит точка (или на каком ребре). Вставляем. Итого у нас появилось несколько новых рёбер. Они все хорошие ({{TODO|t=Доказать, почему}}), плохими могут оказаться только рёбра, противолежащие вставленной точке. Флипаем рёбра, пока триангуляция не станет хорошей.

Среднее число флипов — <tex>O(1)</tex> ({{TODO|t=Доказать, почему}}). Поэтому время вставки целиком зависит от времени локализации.
==== Вставка точки, лежащей снаружи триангуляции ====
Представим, что вне триангуляции — бесконечные треугольники, основания которых — рёбра выпуклой оболочки триангуляции, а противолежащая ребру вершина — это бесконечно удалённая точка. Тогда понятно, что вставка точки, не лежащей в триангуляции, сведётся к вставке точки внутрь триангуляции, если мы научимся обрабатывать бесконечные фейсы.

{{TODO|t=Написать про бесконечно удалённую точку}}

=== Удаление точки ===
При удалении точки получится {{Acronym|звёздный многоугольник, который можно затриангулировать за линию|Почему на эту тему нет конспекта? Я не собираюсь тут это доказывать}}. Дальше по традиции флипаем всё, что могло стать плохим, пока не получим хорошую триангуляцию.

Средняя степень вершины в триангуляции — <tex>O(1)</tex> ({{TODO|t=Почему?}} — почти то, что нужно, здесь [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D0%B8%D1%80%D0%BA%D0%BF%D0%B0%D1%82%D1%80%D0%B8%D0%BA%D0%B0_%D0%B4%D0%B5%D1%82%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D1%82%D1%80%D0%B8%D0%B0%D0%BD%D0%B3%D1%83%D0%BB%D1%8F%D1%86%D0%B8%D0%B8#.D0.92.D1.8B.D0.B1.D0.BE.D1.80_.D0.BC.D0.BD.D0.BE.D0.B6.D0.B5.D1.81.D1.82.D0.B2.D0.B0_.D1.83.D0.B4.D0.B0.D0.BB.D1.8F.D0.B5.D0.BC.D1.8B.D1.85_.D0.B2.D0.B5.D1.80.D1.88.D0.B8.D0.BD]. Потом пишем <tex>\sum_{v \in V}{deg(v)} = 2E</tex>, делим на <tex>|V|</tex> и получаем <tex>avg(deg(v)) = \frac{O(|V|)}{|V|} = O(1)</tex>), поэтому триангуляция звёздного многоугольника будет тоже за <tex>O(1)</tex>. С флипами всё тоже, в общем-то, хорошо. Итого удаление точки работает за <tex>O(1)</tex>.

== Локализационная структура ==
=== Сама структура ===
В общем-то, довольно стандартная схема для рандомизированных структур: на нижнем уровне содержатся все точки; каждая точка с вероятностью p проходит на следующий уровень.
=== Локализация ===
Как происходит локализация: нам дают точку <tex>v_{i+1}</tex>, которая на предыдущем уровне была ближайшей к точке <tex>q</tex>, которую мы локализуем. Нужно получить следующую точку <tex>v_i</tex>, которая будет ближайшей уже на этом уровне. Делается это следующим образом:
* Находим, в каком из треугольников, смежных с <tex>v_{i+1}</tex>, лежит отрезок <tex>v_{i+1} q</tex>
* Находим, какие рёбра треугольников пересекает <tex>v_{i+1} q</tex>, в итоге находим треугольник, в котором лежит <tex>q</tex>
* Находим ближайшую к <tex>q</tex> точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к <tex>q</tex> вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к <tex>q</tex> — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая.

{{Теорема
|statement=Данный алгоритм найдёт ближайшую точку.
|proof=
{{TODO|t=Картинку для ясности}}
Предположим, что это не так. Назовём локализуемую точку <tex>q</tex>, а последнего кандидата на то, чтобы быть ближайшей точкой — <tex>v</tex>. Раз эта точка на самом деле не ближайшая, то в окружности, проходящей через <tex>v</tex>, с центром в точке <tex>q</tex> найдутся ещё какие-то точки, не смежные с <tex>v</tex>. Рассмотрим ближайшую из них к <tex>v</tex>: точку <tex>v'</tex>. Построим на <tex>vv'</tex> окружность как на диаметре. В этой окружности не будет лежать никаких точек, так как мы взяли ближайшую. Значит, ребро <tex>vv'</tex> удовлетворяет критерию Делоне и должно являться ребром триангуляции, но по предположению этого ребра нет. Значит, предположение неверно.
}}

=== Профит ===
{{TODO|t=Время работы, требуемая память}}

== Constraints ==
{{Определение
|definition=
'''Констрейнты''' — рёбра, которые нельзя флипать
}}
{{Утверждение
|statement=
Хорошая триангуляция с констрейнтом может быть хорошей с точностью до видимости через констрейнт
}}
=== Вставка ===
Смотрим на список рёбер, пересечённых ещё не вставленным констрейнтом ({{TODO|t=Картинку бы}}), и флипаем их. Последнее флипнутое ребро и будет констрейнтом {{Acronym|(по понятным причинам)|Рёбра, пересечённые констрейнтом, после флипа будут начинаться в той же точке, что и констрейнт, а заканчиваться в точке, в которой начинается ещё одно пересекающее ребро. Последнее же ребро будет начинаться и заканчиваться в начале и конце констрейнта}}, после флипа пометим его как констрейнт. Понятное дело, критерий «хорошести» ребра при таких фокусах немного изменится: туда добавится проверка на то, не является ли ребро констрейнтом. Затем флипаем всё, что могло стать плохим (кроме констрейнта), пока триангуляция вновь не станет условно хорошей.

{{TODO|t=Тут должно быть ещё несколько упоительных фактов про то, что вставка производится за <tex>O(k^2)</tex>, где <tex>k</tex> — число пересечённых рёбер, и про то, что, если флипать что попало, можно нарваться на флип в невыпуклом многоугольнике}}

=== Удаление ===
Аналогично: помечаем ребро как не-констрейнт и начинаем флипать, пока не дойдём до хорошей (или условно хорошей) триангуляции.

Работает оно столько же, сколько и вставка, ибо всё, что мы нафлипали при вставке, нужно перефлипать обратно.

=== Констрейнты в локализационной структуре ===
В локализационную структуру констрейнты нужно вставлять только на нижний уровень, ибо выше они нафиг не нужны.

Викиконспекты - Вклад участника [ru]

Триангуляция Делоне