355
правок
Изменения
м
{{Определение
|definition='''Критерий Делоне для ребра''': на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.
}}
{{Лемма
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
|proof=
То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне).
Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне.
{{TODO|t=Надо вставить картинку}}
Предположим, что это ребро (назовём его <tex>AB</tex>) не принадлежит триангуляции Делоне. Тогда существует пересекающее его ребро <tex>CD</tex>, принадлежащее триангуляции. Рассмотрим четырёхугольник <tex>ACBD</tex>. Точки <tex>C</tex> и <tex>D</tex> лежат вне окружности, построенной на <tex>AB</tex> как на хорде, поэтому сумма углов <tex>C</tex> и <tex>D</tex> меньше 180°. Аналогичным образом доказывается, что сумма углов <tex>A</tex> и <tex>B</tex> тоже меньше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> меньше 360°, что невозможно. Противоречие. Значит, ребро <tex>AB</tex> принадлежит триангуляции Делоне.
}}
Нет описания правки
'''Триангуляция Делоне''' — триангуляция, являющаяся подразбиением Делоне.
}}
== Существование триангуляции Делоне ==
{{Лемма
Из единственности выпуклой оболочки следует, что такое подразбиение единственно.
}}
== Критерий Делоне для рёбер ==
{{Определение
|definition='''Критерий Делоне для ребра''': на ребре можно построить такую окружность, что внутри неё не будет лежать никаких точек.
}}
{{Лемма
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
|proof=
То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне).
Докажем, что если для ребра выполняется критерий Делоне, то оно принадлежит триангуляции Делоне.
{{TODO|t=Надо вставить картинку}}
Предположим, что это ребро (назовём его <tex>AB</tex>) не принадлежит триангуляции Делоне. Тогда существует пересекающее его ребро <tex>CD</tex>, принадлежащее триангуляции. Рассмотрим четырёхугольник <tex>ACBD</tex>. Точки <tex>C</tex> и <tex>D</tex> лежат вне окружности, построенной на <tex>AB</tex> как на хорде, поэтому сумма углов <tex>C</tex> и <tex>D</tex> меньше 180°. Аналогичным образом доказывается, что сумма углов <tex>A</tex> и <tex>B</tex> тоже меньше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> меньше 360°, что невозможно. Противоречие. Значит, ребро <tex>AB</tex> принадлежит триангуляции Делоне.
}}
== Динамическая триангуляция ==
* Находим ближайшую к <tex>q</tex> точку. Первым кандидатом на то, чтобы быть ближайшей точкой, становится ближайшая к <tex>q</tex> вершина найденного в предыдущем пункте треугольника. Для каждого кандидата нужно просмотреть смежные вершины в поиске точки, которая находится ближе к <tex>q</tex> — эта точка становится следующим кандидатом. Если же среди соседей точки не нашлось более близких, значит, эта точка и есть ближайшая.
=== Корректность алгоритма ===
{{Теорема
|statement=Данный алгоритм найдёт ближайшую точку.
