What is the worst case of the randomized incremental delaunay triangulation algorithm?
The first approach can be formalized as follows.

Let $P$ be an arbitrary set of $n$ points on the positive branch of the parabola $y=x^2$; that is,
$$
P = \{ (t_1, t_1^2), (t_2, t_2^2), \dots, (t_n, t_n^2) \}
$$
for some positive real numbers $t_1, t_2, \dots, t_n$.  Without loss of generality, assume these points are indexed in increasing order: $0 &lt; t_1 &lt; t_2 &lt; \cdots &lt; t_n$.

Claim: In the Delaunay triangulation of $P$, the leftmost point $(t_1, t_1^2)$ is a neighbor of every other point in $P$.

This claim implies that adding a new point $(t_0, t_0^2)$ to $P$ with $0 &lt; t_0 &lt; t_1$ adds $n$ new edges to the Delaunay triangulation.  Thus, inductively, if we incrementally contract the Delaunay triangulation of $P$ by inserting the points in right-to-left order, the total number of Delaunay edges created is $\Omega(n^2)$.



We can prove the claim as follows.  For any real values $0&lt;a&lt;b&lt;c$, let $C(a,b,c)$ denote the unique circle through the points $(a,a^2), (b,b^2), (c,c^2)$.

Lemma: $C(a,b,c)$ does not contain any point $(t,t^2)$ where $a&lt;t&lt;b$ or $c&lt;t$.

Proof: Recall that four points $(a,b), (c,d), (e,f), (g,h)$ are cocircular if and only if 
$$
\begin{vmatrix}
1 &amp; a &amp; b &amp; a^2 + b^2 \\
1 &amp; c &amp; d &amp; c^2 + d^2 \\
1 &amp; e &amp; f &amp; e^2 + f^2 \\
1 &amp; g &amp; h &amp; g^2 + h^2 \\
\end{vmatrix}
=
0
$$
Thus, a point $(t,t^2)$ lies on the circle $C(a,b,c)$ if and only if
$$
\begin{vmatrix}
1 &amp; a &amp; a^2 &amp; a^2 + a^4 \\
1 &amp; b &amp; b^2 &amp; b^2 + b^4 \\
1 &amp; c &amp; c^2 &amp; c^2 + c^4 \\
1 &amp; t &amp; t^2 &amp; t^2 + t^4 \\
\end{vmatrix}
=
0
$$
It's not hard (for example, ask Wolfram Alpha) to expand and factor the $4\times4$ determinant into the following form:
$$
(a-b)(a-c)(b-c)(a-t)(b-t)(c-t)(a+b+c+t) = 0
\tag{$*$}
$$
Thus, $(t,t^2)$ lies on $C(a,b,c)$ if and only if $t=a$, $t=b$, $t=c$, or $t=-a-b-c &lt; 0$.  Moreover, because $0&lt;a&lt;b&lt;c$, these four roots are distinct, which implies that the parabola actually crosses $C(a,b,c)$ at those four points.  It follows that $(t,t^2)$ lies inside $C(a,b,c)$ if and only if $-a-b-c&lt;t&lt;a$ or $b&lt;t&lt;c$.$\qquad\Box$