Qual é o pior caso do algoritmo de triangulação incremental aleatória delaunay?

9

Eu sei que o esperado pior caso de tempo de execução do randomizado incrementais Delaunay triangulação algoritmo (como indicado no Computational Geometry ) é . Há um exercício que implica que o pior tempo de execução é . Eu tentei construir um exemplo em que esse é realmente o caso, mas ainda não obtive sucesso.O(nregistron)Ω(n2)

Uma dessas tentativas foi organizar e ordenar o ponto definido de maneira que, ao adicionar um ponto na etapa , sejam criadas cerca de arestas.prrr-1 1

Outra abordagem pode envolver a estrutura de localização do ponto: tente organizar os pontos de forma que o caminho percorrido na estrutura de localização do ponto para localizar um ponto na etapa seja o maior possível.prr

Ainda assim, não tenho certeza de qual dessas duas abordagens está correta (se houver) e ficaria feliz em algumas dicas.

Tedil
fonte
3
Tente colocar todos os pontos na curva para alguns bem escolhido r . y=xrr
27612 Peter Shor

Respostas:

9

A primeira abordagem pode ser formalizada da seguinte maneira.

Seja um conjunto arbitrário de n pontos no ramo positivo da parábola y = x 2 ; isto é, P = { ( t 1 , t 2 1 ) , ( t 2 , t 2 2 ) , , ( t n , t 2 n ) } para alguns números reais positivos t 1 , t 2 , , t nPny=x2

P={(t1 1,t1 12),(t2,t22),...,(tn,tn2)}
t1,t2,,tn. Sem perda de generalidade, suponha que esses pontos sejam indexados em ordem crescente: .0<t1<t2<<tn

Reivindicação: Na triangulação Delaunay de , o ponto mais à esquerda ( t 1 , t 2 1 ) é um vizinho de todos os outros pontos em P .P(t1,t12)P

Esta alegação implica que adicionar um novo ponto a P com 0 < t 0 < t 1 adiciona n novas arestas à triangulação de Delaunay. Assim, indutivamente, se contratarmos de forma incremental a triangulação de Delaunay de P , inserindo os pontos na ordem da direita para a esquerda , o número total de arestas de Delaunay criadas será Ω ( n 2 ) .(t0,t02)P0<t0<t1nPΩ(n2)


Podemos provar a reivindicação da seguinte forma. Para quaisquer valores reais , deixe C ( a , b , c ) denotar o círculo único através dos pontos ( a , a 2 ) , ( b , b 2 ) , ( c , c 2 ) .0<a<b<cC(a,b,c)(a,a2),(b,b2),(c,c2)

C(a,b,c)(t,t2)a<t<bc<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
4×4
()(ab)(ac)(bc)(at)(bt)(ct)(a+b+c+t)=0
(t,t2)C(a,b,c)t=at=bt=ct=abc<00<a<b<cC(a,b,c)(t,t2) C(a,b,c)abc<t<ab<t<c
Jeffε
fonte
Obrigado, mesmo que eu realmente queria apenas uma sugestão (sem a prova);)
Tedil