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.
Uma dessas tentativas foi organizar e ordenar o ponto definido de maneira que, ao adicionar um ponto na etapa , sejam criadas cerca de arestas.
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.
Ainda assim, não tenho certeza de qual dessas duas abordagens está correta (se houver) e ficaria feliz em algumas dicas.
Respostas:
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 nP n y= x2
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,t21) 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,t20) P 0<t0<t1 n P Ω(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<c C(a,b,c) (a,a2),(b,b2),(c,c2)
fonte