<p>The first approach can be formalized as follows.</p>

<p>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$.</p>

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

<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 <em>in right-to-left order</em>, the total number of Delaunay edges created is $\Omega(n^2)$.</p>

<hr>

<p>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)$.</p>

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

<p><strong>Proof:</strong> 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 <em>inside</em> $C(a,b,c)$ if and only if $-a-b-c&lt;t&lt;a$ or $b&lt;t&lt;c$.$\qquad\Box$</p>

CC BY-SA 3.0
2012-07-27T17:29:57.197Z
Thank you, even though I actually only wanted a hint (without the proof) ;)
Tedil
CC BY-SA 3.0
2012-07-27T15:35:58.923Z
2012-07-27T15:35:58.923Z
Jeffε
<p>I know that the <em>expected</em> worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in <a href="http://www.cs.uu.nl/geobook/">Computational Geometry</a>) 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.</p>

<p>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.</p>

<p>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.</p>

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

CC BY-SA 3.0
2012-07-27T15:04:40.457Z
Try putting all the points on the curve $y = x^r$ for some well-chosen $r$.
Peter Shor 
<ds.algorithms><randomized-algorithms><delaunay-triangulation><worst-case>
What is the worst case of the randomized incremental delaunay triangulation algorithm?
Tedil
# What is the worst case of the randomized incremental delaunay triangulation algorithm?

(Asked by: username_0 on 2012-07-27)

I know that the *expected* worst-case runtime of the randomized incremental delaunay triangulation algorithm (as given in [Computational Geometry](http://www.cs.uu.nl/geobook/)) 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.

**Tags:** ds.algorithms, randomized-algorithms, delaunay-triangulation, worst-case

> **Comments:**
> **username_1**: Try putting all the points on the curve $y = x^r$ for some well-chosen $r$.  

---

## 1 answers

### Answer by username_2 on 2012-07-27. Score: 10 | Accepted answer

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

**Lemma:** *$C(a,b,c)$ does not contain any point $(t,t^2)$ where $a*

**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 $0inside $C(a,b,c)$ if and only if $-a-b-c

> **Comments:**
> **username_0**: Thank you, even though I actually only wanted a hint (without the proof) ;)  

---

