355
правок
Изменения
м
== Динамическая триангуляция ==
→Некоторые упоительные факты
Из единственности выпуклой оболочки следует, что такое подразбиение единственно.
}}
== Некоторые упоительные факты Динамическая триангуляция =={{TODO|t=Раскидать это всё в те разделы, где это нужно}}{{Определение|definition='''Критерий Делоне для ребра''' — на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.}}{{Лемма|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне|proof=То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне). Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне.{{TODO|t=А как это вообще доказывается?}}}}
{{Определение
|definition=Ребро назовём '''хорошим''', если для пары треугольников, которым принадлежит это ребро, выполняется критерий Делоне (то есть вершина, противолежащая ребру в одном треугольнике, не лежит в окружности, описанной вокруг другого, и наоборот)
Очевидно, потому что каждый флип уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
}}
=== Вставка точки ===
==== Вставка точки, лежащей внутри триангуляции ====
* Находим, какие рёбра треугольников пересекает <tex>v_{i+1} q</tex>, в итоге находим треугольник, в котором лежит <tex>q</tex>
* Находим ближайшую к <tex>q</tex> точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к <tex>q</tex> вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к <tex>q</tex> — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая.
{{Определение
|definition='''Критерий Делоне для ребра''' — на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.
}}
{{Лемма
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне
|proof=
То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне).
Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне.
{{TODO|t=А как это вообще доказывается?}}
}}
{{Теорема
|statement=Данный алгоритм найдёт ближайшую точку.
