355
правок
Изменения
→Динамическая триангуляция
Для пары смежных треугольников '''flip''' — убирание смежного ребра и проведение другого.
}}
[[Файл:Flip.png|400px|thumb|right|Красное ребро — до флипа, синее — после]]
Из [[#fliplemma|леммы]] следует, что если ребро плохое, то флип сделает его хорошим.
{{Лемма
|statement=Флип плохого ребра уменьшает разность объёмов параболоида и триангуляции, спроецированной на него.
|id=volumelemma
|proof={{TODO|t=Доказать}}Рассмотрим два таких смежных треугольника, что ребро между ними является плохим. Спроецируем их на параболоид. Четыре точки, принадлежащие смежным треугольникам, при проекции на параболоид образуют тетраэдр. Проведём через какой-нибудь из двух треугольников плоскость. Вершина, противолежащая основанию тетраэдра, являющегося этим треугольником, лежит ниже этой плоскости (так как не выполняется локальный критерий Делоне), то есть тетраэдр лежит ниже тела, образующегося при проекции всей триангуляции на параболоид. После флипа станет выполняться локальный критерий Делоне, то есть тело станет включать в себя тетраэдр. Поэтому после флипа плохого ребра объём тела увеличится на объём этого тетраэдра.
}}
{{Лемма
