# What is the worst case of the randomized incremental delaunay triangulation algorithm?

I know that the expected worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in Computational Geometry) is $\mathcal O(n \log n)$. There is an exercise which implies the worst-case runtime is $\Omega(n^2)$. I've tried to construct an example where this actually is the case but haven't been successful so far.

One of those tries was to arrange and order the point set in a manner such that, when adding a point $p_r$ in step $r$, about $r-1$ edges are created.

Another approach might involve the point-location structure: Try to arrange the points such that the path taken in the point-location structure for locating a point $p_r$ in step $r$ is as long as possible.

Still, I'm unsure which of these two approaches is correct (if at all) and would be glad for some hints.

• Try putting all the points on the curve $y = x^r$ for some well-chosen $r$. – Peter Shor Jul 27 '12 at 15:04

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 < t_1 < t_2 < \cdots < 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 < t_0 < 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<a<b<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<t<b$ or $c<t$.

Proof: Recall that four points $(a,b), (c,d), (e,f), (g,h)$ are cocircular if and only if $$\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$$ Thus, a point $(t,t^2)$ lies on the circle $C(a,b,c)$ if and only if $$\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$$ 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 < 0$. Moreover, because $0<a<b<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<t<a$ or $b<t<c$.$\qquad\Box$

• Thank you, even though I actually only wanted a hint (without the proof) ;) – Tedil Jul 27 '12 at 17:29