Apa kasus terburuk dari algoritma triangulasi delaunay inkremental acak?

Saya tahu bahwa runtime kasus terburuk yang diharapkan dari algoritma triangulasi delaunay inkremental acak (seperti yang diberikan dalam Computational Geometry ) adalah . Ada latihan yang menyiratkan runtime kasus terburuk adalah . Saya sudah mencoba membangun contoh di mana ini sebenarnya terjadi tetapi belum berhasil sejauh ini.$\mathcal O(n \log n)$$\Omega(n^2)$

Salah satu dari percobaan tersebut adalah mengatur dan memesan titik yang diatur sedemikian rupa sehingga, saat menambahkan titik pada langkah , tentang tepi dibuat.$p_r$$r$$r-1$

Pendekatan lain mungkin melibatkan struktur titik-lokasi: Cobalah untuk mengatur titik-titik sehingga jalur yang diambil dalam struktur titik-lokasi untuk menemukan titik dalam langkah adalah selama mungkin.$p_r$$r$

Namun, saya tidak yakin yang mana dari dua pendekatan ini yang benar (jika sama sekali) dan akan senang untuk beberapa petunjuk.

Pendekatan pertama dapat diformalkan sebagai berikut.

Membiarkan $P$ menjadi set sewenang-wenang $n$ poin pada cabang positif parabola $y=x^2$; itu adalah,

$$P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \}$$ untuk beberapa bilangan real positif $t_1, t_2, \dots, t_n$. Tanpa kehilangan sifat umum, anggap poin-poin ini diindeks dalam urutan yang meningkat:$0 < t_1 < t_2 < \cdots < t_n$.

Klaim: Dalam triangulasi Delaunay$P$, titik paling kiri $(t_1, t_1^2)$ adalah tetangga dari setiap titik lain di $P$.

Klaim ini menyiratkan bahwa menambahkan titik baru $(t_0, t_0^2)$ untuk $P$ dengan $0 < t_0 < t_1$ menambahkan $n$tepi baru untuk triangulasi Delaunay. Jadi, secara induktif, jika kita secara bertahap mengontrak triangulasi Delaunay$P$dengan memasukkan titik-titik dalam urutan kanan-ke-kiri , jumlah total tepi Delaunay dibuat adalah$\Omega(n^2)$.

---

Kami dapat membuktikan klaim sebagai berikut. Untuk nilai nyata apa pun$0<a<b<c$biarkan $C(a,b,c)$ menunjukkan lingkaran unik melalui titik-titik $(a,a^2), (b,b^2), (c,c^2)$.

Kata pengantar singkat: $C(a,b,c)$ tidak mengandung poin apa pun $(t,t^2)$ dimana $a<t<b$ atau $c<t$.

Bukti: Ingat bahwa empat poin$(a,b), (c,d), (e,f), (g,h)$ adalah cocircular jika dan hanya jika

$$\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$$ Jadi, sebuah poin $(t,t^2)$ terletak di lingkaran $C(a,b,c)$ jika dan hanya jika $$\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$$ Tidak sulit (misalnya, minta Wolfram Alpha) untuk memperluas dan memfaktorkannya $4\times4$ penentu ke dalam formulir berikut: $$(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0 \tag{$*$}$$ Jadi, $(t,t^2)$ terletak pada $C(a,b,c)$ jika dan hanya jika $t=a$, $t=b$, $t=c$, atau $t=-a-b-c < 0$. Apalagi karena$0<a<b<c$, keempat akar ini berbeda, yang menyiratkan bahwa parabola sebenarnya bersilangan $C(a,b,c)$di empat titik. Karena itu$(t,t^2)$terletak di dalam $C(a,b,c)$ jika dan hanya jika $-a-b-c<t<a$ atau $b<t<c$.$\qquad\Box$