Каков наихудший случай алгоритма рандомизированной инкрементной триангуляции Делоне?

9

Я знаю, что ожидаемое время выполнения алгоритма рандомизированного инкрементального инкрементального триангуляции Делоне (как указано в « Вычислительной геометрии» ) составляет . Существует упражнение, которое подразумевает, что наихудший вариант выполнения - . Я попытался построить пример, где это действительно так, но пока не удалось.O(nlogn)Ω(n2)

Одна из этих попыток состояла в том, чтобы упорядочить и упорядочить набор точек таким образом, чтобы при добавлении точки на шаге создавалось около ребер .prrr1

Другой подход может включать структуру расположения точек: расположить точки так, чтобы путь, пройденный в структуре размещения точек для определения местоположения точки на шаге был как можно более длинным.prr

Тем не менее, я не уверен, какой из этих двух подходов является правильным (если вообще есть), и был бы рад некоторым подсказкам.

Tedil
источник
3
Попробуйте поставить все точки на кривой y=xr для некоторых удачно выбранных r,
Питер Шор

Ответы:

9

Первый подход может быть формализован следующим образом.

Позволять P быть произвольным набором n указывает на положительную ветвь параболы y=x2; это,

P={(t1,t12),(t2,t22),,(tn,tn2)}
для некоторых положительных действительных чисел t1,t2,,tn, Без ограничения общности предположим, что эти точки проиндексированы в порядке возрастания:0<t1<t2<<tn,

Утверждение: в триангуляции ДелонеPкрайняя левая точка (t1,t12) сосед любой другой точки в P,

Это утверждение подразумевает, что добавление нового пункта (t0,t02) в 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) коциркулярны тогда и только тогда, когда

|1aba2+b21cdc2+d21efe2+f21ghg2+h2|=0
Таким образом, точка (t,t2) лежит на круге C(a,b,c) если и только если
|1aa2a2+a41bb2b2+b41cc2c2+c41tt2t2+t4|=0
Нетрудно (например, спросить Wolfram Alpha) расширить и 4×4 определитель в следующей форме:
()(ab)(ac)(bc)(at)(bt)(ct)(a+b+c+t)=0
Таким образом, (t,t2) лежит на C(a,b,c) если и только если t=a, t=b, t=c, или t=abc<0, Более того, потому что0<a<b<cэти четыре корня различны, что означает, что парабола фактически пересекает C(a,b,c)в этих четырех точках. Это следует из того(t,t2)лежит внутри C(a,b,c) если и только если abc<t<a или b<t<c,
Jeffε
источник
Спасибо, хотя я на самом деле хотел только подсказку (без доказательства);)
Тедил