Я знаю, что ожидаемое время выполнения алгоритма рандомизированного инкрементального инкрементального триангуляции Делоне (как указано в « Вычислительной геометрии» ) составляет . Существует упражнение, которое подразумевает, что наихудший вариант выполнения - . Я попытался построить пример, где это действительно так, но пока не удалось.
Одна из этих попыток состояла в том, чтобы упорядочить и упорядочить набор точек таким образом, чтобы при добавлении точки на шаге создавалось около ребер .
Другой подход может включать структуру расположения точек: расположить точки так, чтобы путь, пройденный в структуре размещения точек для определения местоположения точки на шаге был как можно более длинным.
Тем не менее, я не уверен, какой из этих двух подходов является правильным (если вообще есть), и был бы рад некоторым подсказкам.
Ответы:
Первый подход может быть формализован следующим образом.
ПозволятьP быть произвольным набором n указывает на положительную ветвь параболы y=x2 ; это,
Утверждение: в триангуляции ДелонеP крайняя левая точка (t1,t21) сосед любой другой точки в P ,
Это утверждение подразумевает, что добавление нового пункта(t0,t20) в P с 0<t0<t1 адды n новые ребра в триангуляции Делоне. Таким образом, индуктивно, если мы постепенно сокращаем триангуляцию ДелонеP вставляя точки в порядке справа налево , общее количество созданных ребер Делоне составляетΩ(n2) ,
Мы можем доказать это утверждение следующим образом. Для любых реальных ценностей0<a<b<c , позволять C(a,b,c) обозначим уникальный круг через точки (a,a2),(b,b2),(c,c2) ,
Лемма:C(a,b,c) не содержит никакой точки (t,t2) где a<t<b или c<t ,
Доказательство: напомним, что четыре очка(a,b),(c,d),(e,f),(g,h) коциркулярны тогда и только тогда, когда
источник