355
правок
Изменения
→Некоторые упоительные факты
Из двух рёбер, которые можно провести для пары треугольников, как минимум одно хорошее
|proof=
Спроецируем четыре точки на параболоид. Очевидно, что по ним можно построить четырёхугольник {{TODOAcronym|t=Доказатьдвумя способами: в первом случае он будет «вогнутым», во втором — «выпуклым»|Если все четыре точки лежат на одной окружности, то оба ребра будут хорошими, так как четырёхугольник можно будет построить только один}}. По доказанному выше факту про окружность, спроецированную на параболоид, выпуклое ребро будет хорошим.
}}
{{Лемма
Для пары смежных треугольников '''flip''' — убирание смежного ребра и проведение другого
}}
Из первой леммы следует, что, если ребро плохое, то флип сделает его хорошим.
{{Лемма
|statement=
Флипами можно достичь хорошей триангуляции за конечное время
|proof=
}}
== Динамическая триангуляция ==
=== Вставка точки ===
