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

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. $\mathcal O(n \log n)$ $\Omega(n^2)$

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. $p_r$ $r$ $r-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. $p_r$ $r$

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

ds.algorithms randomized-algorithms delaunay-triangulation worst-case Tedil
quelle

Versuchen Sie, alle Punkte auf der Kurve

y = x^{r}

$y = x^r$ für ein gut ausgewähltes

r

$r$ .

Peter Shor

Der erste Ansatz kann wie folgt formalisiert werden.

Sei eine beliebige Menge von Punkten auf dem positiven Zweig der Parabel ; das heißt, für einige positive reelle Zahlen $P$ $n$ $y=x^2$

P. = {(t_{1}, t_{1}^{2}), (t_{2}, t_{2}^{2}), \dots, (t_{n}, t_{n}^{2})}}

$P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \}$

t_{1}, t_{2}, \dots, t_{n}

$t_1, t_2, \dots, t_n$ . Nehmen Sie ohne Verlust der Allgemeinheit an, dass diese Punkte in aufsteigender Reihenfolge indiziert sind:

0 < t_{1} < t_{2} < \dots < t_{n}

$0 < t_1 < t_2 < \cdots < t_n$

Ansprüche: In der Delaunay Triangulation von , den am weitesten links liegende Punkt ist ein Nachbar von jedem anderen Punkt in . $P$ $(t_1, t_1^2)$ $P$

Diese Behauptung impliziert, dass das Hinzufügen eines neuen Punktes zu mit der Delaunay-Triangulation neue Kanten hinzufügt . Wenn wir also die Delaunay-Triangulation von durch Einfügen der Punkte in der Reihenfolge von rechts nach links inkrementell kontrahieren , beträgt die Gesamtzahl der erzeugten Delaunay-Kanten . $(t_0, t_0^2)$ $P$ $0 < t_0 < t_1$ $n$ $P$ $\Omega(n^2)$

$0<a<b<c$ $C(a,b,c)$ $(a,a^2), (b,b^2), (c,c^2)$

$C(a,b,c)$ $(t,t^2)$ $a<t<b$ $c<t$

$(a,b), (c,d), (e,f), (g,h)$

| \begin{matrix} 1 & ein & b & {ein}^{2} + b^{2} \\ 1 & c & d & c^{2} + d^{2} \\ 1 & e & f & e^{2} + f^{2} \\ 1 & G & h & G^{2} + h^{2} \end{matrix} | = 0

$\begin{vmatrix} 1 & a & b & a^2 + b^2 \\ 1 & c & d & c^2 + d^2 \\ 1 & e & f & e^2 + f^2 \\ 1 & g & h & g^2 + h^2 \\ \end{vmatrix} = 0$

(t, t^{2})

$(t,t^2)$

C (a, b, c)

$C(a,b,c)$

| \begin{matrix} 1 & ein & {ein}^{2} & {ein}^{2} + {ein}^{4} \\ 1 & b & b^{2} & b^{2} + b^{4} \\ 1 & c & c^{2} & c^{2} + c^{4} \\ 1 & t & t^{2} & t^{2} + t^{4} \end{matrix} | = 0

$\begin{vmatrix} 1 & a & a^2 & a^2 + a^4 \\ 1 & b & b^2 & b^2 + b^4 \\ 1 & c & c^2 & c^2 + c^4 \\ 1 & t & t^2 & t^2 + t^4 \\ \end{vmatrix} = 0$

4 \times 4

$4\times4$

\begin{matrix} (*) & (ein - - b) (ein - - c) (b - - c) (ein - - t) (b - - t) (c - - t) (ein + b + c + t) = 0 \end{matrix}

$(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0 \tag{$*$}$

(t, t^{2})

$(t,t^2)$

C (a, b, c)

$C(a,b,c)$

t = a

$t=a$

t = b

$t=b$

t = c

$t=c$

t = - a - b - c < 0

$t=-a-b-c < 0$

0 < a < b < c

$0<a<b<c$

C (a, b, c)

$C(a,b,c)$

(t, t^{2})

$(t,t^2)$

C (a, b, c)

$C(a,b,c)$

- a - b - c < t < a

$-a-b-c<t<a$

b < t < c

$b<t<c$

◻

$\qquad\Box$

Jeffε
quelle

Danke, obwohl ich eigentlich nur einen Hinweis wollte (ohne den Beweis);)

Tedil

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

Antworten: