355
правок
Изменения
→Динамическая триангуляция
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее.
|proof=
[[Файл:Bad edges.png|400px|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°, что невозможно.
}}
{{Лемма
|statement=
Если все рёбра хорошие, то и триангуляция хорошая.
|proof=
}}
{{Определение
|definition=
Для пары смежных треугольников '''flip''' — убирание смежного ребра и проведение другого.
}}
{{Лемма
|statement=
Флипами можно достичь хорошей триангуляции за конечное время.
|proof=
Очевидно, потому что каждый флип уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
