9
$\begingroup$

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.

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

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$

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.