¿Cuál es el peor caso del algoritmo de triangulación incremental aleatorio delaunay?

Sé que el tiempo de ejecución esperado en el peor de los casos del algoritmo de triangulación incremental aleatorio delaunay (como se da en Computational Geometry ) es . Hay un ejercicio que implica que el peor tiempo de ejecución es . He tratado de construir un ejemplo donde este sea realmente el caso, pero hasta ahora no he tenido éxito.$\mathcal O(n \log n)$$\Omega(n^2)$

Uno de esos intentos fue organizar y ordenar el conjunto de puntos de tal manera que, al agregar un punto $p_r$ en el paso $r$ , se crean aproximadamente $r-1$ aristas.

Otro enfoque podría involucrar la estructura de ubicación de puntos: intente organizar los puntos de modo que el camino tomado en la estructura de ubicación de puntos para ubicar un punto $p_r$ en el paso $r$ sea ​​lo más largo posible.

Aún así, no estoy seguro de cuál de estos dos enfoques es correcto (si es que lo hace) y me alegraría por algunas sugerencias.

El primer enfoque se puede formalizar de la siguiente manera.

Sea un conjunto arbitrario de n puntos en la rama positiva de la parábola y = x 2 ; es decir, P = { ( t 1 , t 2 1 ) , ( t 2 , t 2 2 ) , ... , ( t n , t 2 n ) } para algunos números reales positivos t 1 , t 2 , ... , t $P$$n$$y=x^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$. Sin pérdida de generalidad, suponga que estos puntos están indexados en orden creciente: .$0 < t_1 < t_2 < \cdots < t_n$

Reclamación: En la triangulación de Delaunay de , el punto más a la izquierda ( t 1 , t 2 1 ) es un vecino de cada otro punto en P .$P$$(t_1, t_1^2)$$P$

Esta afirmación implica que agregar un nuevo punto a P con 0 < t 0 < t 1 agrega n nuevas aristas a la triangulación de Delaunay. Por lo tanto, inductivamente, si contraemos incrementalmente la triangulación de Delaunay de P insertando los puntos en orden de derecha a izquierda , el número total de bordes de Delaunay creados es Ω ( n 2 ) .$(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)$

Lema: no contiene ningún punto ( t , t 2 ) donde a < t < b o c < t .$C(a,b,c)$$(t,t^2)$$a<t<b$$c<t$

Prueba: recuerde que cuatro puntos son cocirculares si y solo si | 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$(a,b), (c,d), (e,f), (g,h)$ Por lo tanto, un punto(t,t2) seencuentra en el círculoC(a,b,c)si y solo si | 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 +

$$\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)$$C(a,b,c)$ $$\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\times4$ $$(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0 \tag{$*$}$$ $(t,t^2)$$C(a,b,c)$$t=a$$t=b$$t=c$$t=-a-b-c < 0$$0<a<b<c$$C(a,b,c)$$(t,t^2)$ $C(a,b,c)$$-a-b-c<t<a$$b<t<c$$\qquad\Box$