Изменения

Перейти к: навигация, поиск

Триангуляция Делоне

829 байт добавлено, 00:47, 14 марта 2014
Динамическая триангуляция
Флипами можно достичь хорошей триангуляции за конечное время.
|proof=
Очевидное следствие из Всего триангуляций заданного множества точек конечное число, и среди них есть триангуляция Делоне. Последовательность флипов плохих рёбер триангуляции образует такую последовательность триангуляций, что разность объёмов параболоида и спроецированной на него триангуляции убывает ([[#volumelemma|леммыпо лемме]]). Эта последовательность конечна (при этом последней в последовательности является триангуляция Делоне), значит, число флипов, требуемых для достижения триангуляции Делоне, тоже конечно.
}}
{{Лемма
355
правок

Навигация