Изменения

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

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

75 байт добавлено, 03:46, 14 февраля 2014
Локальный критерий Делоне
|proof=
[[Файл:Bad triangle.png|400px|thumb|right|Все рёбра треугольника хорошие, но описанная окружность содержит точки]]
Предположим, что это не так, то есть все рёбра хорошие, но существует треугольниксуществуют треугольники, описанная окружность которого содержит которых содержат какие-либо точки триангуляции. Возьмём какую-либо конфликтную точку <tex>E</tex>. Рассмотрим ребро (пусть это будет такой треугольник <tex>BCABC</tex>)из тех, отрезающее сегмент, содержащий точки, и выберем из этих точек такую точку в описанную окружность которых попадает <tex>DE</tex>, что угол <tex>BEC</tex> максимален, если <tex>BC</tex> — ближайшая к точке <tex>E</tex> сторона. Пусть треугольник <tex>BDC</tex> максимален— смежный с <tex>ABC</tex>. Так как Очевидно, что угол <tex>BDCBED</tex> максималенбольше, то точка чем угол <tex>DBEC</tex> является вершиной смежного с . При этом точка <tex>ABCE</tex> треугольника (лежит в противном случае в треугольнике окружности, описанной вокруг <tex>BCDBDC</tex> будут лежать какие-либо точки, что невозможно по построению({{TODO|t=Почему?}}). Значит, ребро при выборе треугольника нужно было взять не <tex>BCABC</tex> плохое, что противоречит условиюа <tex>BDC</tex>. Значит, предположение неверноПротиворечие.
}}
 
== Динамическая триангуляция ==
{{Определение
355
правок

Навигация