Quel est le pire des cas de l'algorithme de triangulation incrémentielle à delaunay randomisé?

9

Je sais que le temps d'exécution le plus défavorable attendu de l'algorithme de triangulation incrémentielle delaunay randomisé (tel que donné dans Computational Geometry ) est . Il y a un exercice qui implique que le pire temps d'exécution est Ω ( n 2 ) . J'ai essayé de construire un exemple où c'est réellement le cas mais qui n'a pas réussi jusqu'à présent.O(nlogn)Ω(n2)

L'une de ces tentatives consistait à organiser et à ordonner l'ensemble de points de telle sorte que, lors de l'ajout d'un point à l'étape r , environ r - 1 bords soient créés.prrr1

Une autre approche pourrait impliquer la structure de localisation de points: Essayez de disposer les points de telle sorte que le chemin emprunté dans la structure de localisation de points pour localiser un point à l'étape r soit aussi long que possible.prr

Pourtant, je ne sais pas laquelle de ces deux approches est correcte (le cas échéant) et je serais heureux de quelques conseils.

Tedil
la source
3
Essayez de mettre tous les points sur la courbe pour un bien choisi r . y=xrr
Peter Shor

Réponses:

9

La première approche peut être formalisée comme suit.

Soit un ensemble arbitraire de n points sur la branche positive de la parabole y = x 2 ; c'est-à-dire P = { ( t 1 , t 2 1 ) , ( t 2 , t 2 2 ) , , ( t n , t 2 n ) } pour certains nombres réels positifs t 1 , t 2 , , t nPny=x2

P={(t1,t12),(t2,t22),,(tn,tn2)}
t1,t2,,tn. Sans perte de généralité, supposons que ces points sont indexés dans l'ordre croissant: .0<t1<t2<<tn

Revendication: Dans la triangulation de Delaunay de , le point le plus à gauche ( t 1 , t 2 1 ) est voisin de chaque autre point P .P(t1,t12)P

Cette affirmation implique que l'ajout d'un nouveau point à P avec 0 < t 0 < t 1 ajoute n nouveaux bords à la triangulation de Delaunay. Ainsi, par induction, si nous contractons progressivement la triangulation de Delaunay de P en insérant les points dans l'ordre de droite à gauche , le nombre total d'arêtes de Delaunay créées est Ω ( n 2 ) .(t0,t02)P0<t0<t1nPΩ(n2)


0<a<b<cC(a,b,c)(a,a2),(b,b2),(c,c2)

C(a,b,c)(t,t2)une<t<bc<t

(une,b),(c,),(e,F),(g,h)

|1unebune2+b21cc2+21eFe2+F21ghg2+h2|=0
(t,t2)C(une,b,c)
|1uneune2une2+une41bb2b2+b41cc2c2+c41tt2t2+t4|=0
4×4
()(une-b)(une-c)(b-c)(une-t)(b-t)(c-t)(une+b+c+t)=0
(t,t2)C(une,b,c)t=unet=bt=ct=-une-b-c<00<une<b<cC(une,b,c)(t,t2) C(une,b,c)-une-b-c<t<uneb<t<c
Jeffε
la source
Merci, même si je ne voulais en fait qu'un indice (sans la preuve);)
Tedil