Количество перестроений в худшем случае после вставки
треугольника и вправду может быть велико.
Но оно конечно, и меньше N (общего числа точек в триангуляции),
а в среднем равно 2,5 — 3,0 в зависимости от вида
распределения исходных данных.
Доказательство зацикливания и конечности тривиально.
Вводим параметр Ss = "сумма минимальных углов всех треугольников" или
Sr "сумма радиусов описанных окружностей всех треугольников".
После перестроения по условию Делоне Ss всегда возрастает,
а Sr всегда уменьшается (это легко доказывается и следует из
определения условия Делоне).
Т.к. эти параметры монотонно изменяются, следовательно, одна и та же
комбинация треугольников никогда не повторится, т.е.
возможность зацикливания исключена.
А т.к. количество всех возможных триангуляций на N точках конечно
(зависит по экспоненте от N), то и перестроения когда-то закончатся.
