418
правок
Изменения
Нет описания правки
|statement=Триангуляции Делоне принадлежат те и только те рёбра (с поправкой на точки, лежащие на одной окружности), которые удовлетворяют критерию Делоне.
|proof=
[[Файл:Good edges.png|400px|thumb200px|right|Для рёбер AB и CD выполняется критерий Делоне, на них построены окружности]]
То, что для рёбер, принадлежащих триангуляции Делоне, выполняется критерий Делоне для рёбер, очевидно (вокруг каждого ребра можно описать окружность, проходящую через противолежащую ему точку в смежном треугольнике, причём в окружности не будет никаких точек по критерию Делоне).
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.
|proof=
[[Файл:Bad edges.png|400px200px|thumb|right|Рёбра AB и BC плохие]]
Предположим, что это не так, то есть оба ребра (назовём их <tex>AB</tex> и <tex>CD</tex>) плохие. Рассмотрим четырёхугольник <tex>ACBD</tex> и окружность, описанную вокруг треугольника <tex>ABC</tex>. Точка <tex>D</tex> лежит внутри этой окружности, значит, сумма углов <tex>C</tex> и <tex>D</tex> больше 180°. Аналогично доказывается, что сумма углов <tex>A</tex> и <tex>B</tex> больше 180°. Значит, сумма углов четырёхугольника <tex>ACBD</tex> больше 360°, что невозможно.
}}
Если для всех рёбер выполняется локальный критерий Делоне, то выполняется и глобальный критерий Делоне.
|proof=
[[Файл:Bad triangle.png|400px200px|thumb|right|Все рёбра треугольника хорошие, но описанная окружность содержит точки]]
Предположим, что это не так, то есть все рёбра хорошие, но существуют треугольники, описанная окружность которых содержат какие-либо точки триангуляции. Возьмём какую-либо конфликтную точку <tex>E</tex>. Рассмотрим такой треугольник <tex>ABC</tex> из тех, в описанную окружность которых попадает <tex>E</tex>, что угол <tex>BEC</tex> максимален, если <tex>BC</tex> — ближайшая к точке <tex>E</tex> сторона. Пусть треугольник <tex>BDC</tex> — смежный с <tex>ABC</tex>.
Рассмотрим пару смежных треугольников. Рёбра этих треугольников образуют четырёхугольник с проведённой в нём диагональю. Операция замены этой диагонали на другую называется '''flip''' ('''флип''').
}}
[[Файл:Flip.png|400px200px|thumb|right|Красное ребро — до флипа, синее — после]]
Из [[#fliplemma|леммы 3]] следует, что если ребро плохое, то флип сделает его хорошим.
{{Лемма
|id=newedgeslemma
|proof=
[[Файл:Good edge.png|400px200px|thumb|right|Точка V вставлена в треугольник ABC]]
Предположим, точка была вставлена не на ребро. Рассмотрим любое из рёбер — пусть это будет ребро <tex>VC</tex>. Проведём окружность, описывающую треугольник <tex>ABC</tex>. По критерию Делоне в ней не будет никаких точек триангуляции. На ребре <tex>VC</tex> можно построить окружность, изнутри касающуюся окружности, описанной вокруг треугольника. В ней тоже нет никаких точек. Значит, для <tex>VC</tex> выполняется критерий Делоне для рёбер, значит, ребро должно принадлежать триангуляции с добавленной точкой <tex>V</tex>, значит, оно хорошее.
