Was ist der schlimmste Fall des randomisierten inkrementellen Delaunay-Triangulationsalgorithmus?

9

Ich weiß, dass die erwartete Worst-Case-Laufzeit des randomisierten inkrementellen Delaunay-Triangulationsalgorithmus (wie in Computational Geometry angegeben ) . Es gibt eine Übung, die impliziert, dass die Laufzeit im schlimmsten Fall . Ich habe versucht, ein Beispiel zu konstruieren, in dem dies tatsächlich der Fall ist, war aber bisher nicht erfolgreich.Ω ( n 2 )Ö(nLogn)Ω(n2)

Einer dieser Versuche bestand darin, den eingestellten Punkt so anzuordnen und zu ordnen, dass beim Hinzufügen eines Punktes in Schritt etwa Kanten erzeugt werden. r r - 1prrr- -1

Ein anderer Ansatz könnte die Punkt-Ort-Struktur beinhalten: Versuchen Sie, die Punkte so anzuordnen, dass der Pfad in der Punkt-Ort-Struktur zum Lokalisieren eines Punktes in Schritt so lang wie möglich ist. rprr

Trotzdem bin ich mir nicht sicher, welcher dieser beiden Ansätze richtig ist (wenn überhaupt) und würde mich über einige Hinweise freuen.

Tedil
quelle
3
Versuchen Sie, alle Punkte auf der Kurve y=xr für ein gut ausgewähltes r .
Peter Shor

Antworten:

9

Der erste Ansatz kann wie folgt formalisiert werden.

Sei eine beliebige Menge von n Punkten auf dem positiven Zweig der Parabel y = x 2 ; das heißt, P = { ( t 1 , t 2 1 ) , ( t 2 , t 2 2 ) , , ( t n , t 2 n ) } für einige positive reelle Zahlen t 1 , t 2 , , t nP.ny=x2

P.={(t1,t12),(t2,t22),,(tn,tn2)}}
t1,t2,,tn. Nehmen Sie ohne Verlust der Allgemeinheit an, dass diese Punkte in aufsteigender Reihenfolge indiziert sind: .0<t1<t2<<tn

Ansprüche: In der Delaunay Triangulation von , den am weitesten links liegende Punkt ( t 1 , t 2 1 ) ist ein Nachbar von jedem anderen Punkt in P .P.(t1,t12)P.

Diese Behauptung impliziert, dass das Hinzufügen eines neuen Punktes zu P mit 0 < t 0 < t 1 der Delaunay-Triangulation n neue Kanten hinzufügt . Wenn wir also die Delaunay-Triangulation von P durch Einfügen der Punkte in der Reihenfolge von rechts nach links inkrementell kontrahieren , beträgt die Gesamtzahl der erzeugten Delaunay-Kanten Ω ( n 2 ) .(t0,t02)P.0<t0<t1nP.Ω(n2)


0<ein<b<cC.(ein,b,c)(ein,ein2),(b,b2),(c,c2)

C.(ein,b,c)(t,t2)ein<t<bc<t

(ein,b),(c,d),(e,f),(G,h)

|1einbein2+b21cdc2+d21efe2+f21GhG2+h2|=0
(t,t2)C.(ein,b,c)
|1einein2ein2+ein41bb2b2+b41cc2c2+c41tt2t2+t4|=0
4×4
()(ein- -b)(ein- -c)(b- -c)(ein- -t)(b- -t)(c- -t)(ein+b+c+t)=0
(t,t2)C.(ein,b,c)t=eint=bt=ct=- -ein- -b- -c<00<ein<b<cC.(ein,b,c)(t,t2) C.(ein,b,c)- -ein- -b- -c<t<einb<t<c
Jeffε
quelle
Danke, obwohl ich eigentlich nur einen Hinweis wollte (ohne den Beweis);)
Tedil