Сложный алгоритм триангуляции Делоне.

В книге Марка де Берга и др. «Вычислительная геометрия: алгоритмы и приложения» описан очень простой алгоритм грубой силы для вычисления триангуляций Делоне. Алгоритм использует понятие недопустимых ребер - ребер, которые могут отсутствовать в допустимой триангуляции Делоне и должны быть заменены некоторыми другими ребрами. На каждом шаге алгоритм просто находит эти недопустимые ребра и выполняет необходимые смещения (называемые переворотами ребер ) до тех пор, пока не будет недопустимых ребер.

Алгоритм юридической триангуляции ( $T$ )

Вход . Некоторые триангуляции $T$ точечного множества $P$ .
Выход . Законный триангуляция $P$ .

в то время как $T$ содержит недопустимое ребро $p_ip_j$
do
$\quad$Пусть $p_i p_j p_k$ и $p_i p_j p_l$ - два треугольника, смежные с $p_ip_j$ .
$\quad$Удалите $p_ip_j$ из $T$ и вместо этого добавьте $p_kp_l$ .
вернуть $T$ .

Я слышал, что этот алгоритм работает в $O(n^2)$ раз в худшем случае; однако мне не ясно, является ли это утверждение правильным или нет. Если да, как можно доказать эту верхнюю границу?

Триангуляцию Делоне можно рассматривать как нижнюю выпуклую оболочку 2-го набора точек, поднятую к параболоиду. Таким образом, если вы берете 2d набор точек и назначьте каждую точку г координата г я = х 2 я + у 2 1 , то проекция нижней выпуклой оболочки в й у -плоскости дает вам триангуляцию Делоне.$(x_i,y_i)$$z$$z_i=x_i^2+y_1^2$$xy$

С этой точки зрения, что значит для ребра быть незаконным? Прежде всего, для каждой триангуляции T мы можем использовать параболические карту , чтобы получить 3d поверхности (триангулированную) , что проекты , вплоть до Т . Конечно, эта поверхность не обязательно является выпуклой, если она будет выпуклой, T будет триангуляцией Делоне. Проще говоря, ребро ( p i , p j ) является препятствием для выпуклости поверхности, вогнутым ребром. Отражая этот край, мы меняем положение на поднятой поверхности только локально. Итак, давайте посмотрим на 4 балла$(p_i,p_j)$$T$$T$$T$$(p_i,p_j)$ . В 3d они образуют тетраэдр, который проецируется вниз на четырехугольник. Поскольку два треугольника p i p j p k и p i p j p l определяют вогнутый край ( p i , p j ) , треугольники p k p l p i и p k p l p j определяют выпуклый край$p_i,p_j,p_k,p_l$$p_ip_jp_k$$p_ip_jp_l$$(p_i,p_j)$$p_kp_lp_i$$p_kp_lp_j$ . Следовательно, отражение неправильного края соответствует замене вогнутого края выпуклым краем при подъеме. Обратите внимание, что этот переворот может превратить другие выпуклые края в вогнутые края.$(p_l,p_k)$

Примечание: изображение не является геометрически правильным и должно рассматриваться только как эскиз.

Пусть - триангуляция после переворота. Поднял поверхность Т ' «содержит» поверхность Т . Под этим я подразумеваю, что если вы наблюдаете две поверхности с плоскости x y, вы видите только треугольники с поверхности T ′ (или треугольники, которые находятся на обеих поверхностях). Можно также сказать, что поверхность T ′ охватывает больше объема. Кроме того, край ( p i , p j ) теперь лежит «за» поднятой поверхностью, индуцированной T ′ при просмотре с плоскости x y .$T'$$T'$$T$$xy$$T'$$T'$$(p_i,p_j)$$T'$$xy$

Во время переворота мы получаем последовательность поверхностей со строго увеличивающимся объемом. Таким образом, ребро лежит «за» всеми этими поверхностями. Следовательно, он никогда не может появиться снова в процессе переворачивания. Поскольку есть только n, выберите 2 возможных ребра, мы имеем не более O ( n 2 ) сальто.$(p_i,p_j)$$n$$O(n^2)$