Brute force Delaunay triangulation algorithm complexity

Question

In the book "Computational Geometry: Algorithms and Applications" by Mark de Berg et al., there is a very simple brute force algorithm for computing Delaunay triangulations. The algorithm uses the notion of illegal edges -- edges that may not appear in a valid Delaunay triangulation and have to be replaced by some other edges. On each step, the algorithm just finds these illegal edges and performs required displacements (called edge flips) till there are no illegal edges.

Algorithm LegalTriangulation($T$)

Input. Some triangulation $T$ of a point set $P$.
Output. A legal triangulation of $P$.

while $T$ contains an illegal edge $p_ip_j$
do
$\quad$ Let $p_i p_j p_k$ and $p_i p_j p_l$ be the two triangles adjacent to $p_ip_j$.
$\quad$ Remove $p_ip_j$ from $T$, and add $p_kp_l$ instead.
return $T$.

I've heard that this algorithm runs in $O(n^2)$ time in worst case; however, it is not clear to me whether this statement is correct or not. If yes, how can one prove this upper bound?

Answer 1

A Delaunay triangulation can be considered as the lower convex hull of the 2d point set lifted to the paraboloid. Thus, if you take your 2d point set and assign to every point $(x_i,y_i)$ a $z$-coordinate $z_i=x_i^2+y_1^2$, then the projection of the lower convex hull into the $xy$-plane gives you the Delaunay triangulation.

Using this perspective, what does it mean for an edge $(p_i,p_j)$ to be illegal? First of all, for every triangulation $T$ we can use the parabolic map to get a 3d (triangulated) surface that projects down to $T$. Of course, this surface is not necessarily convex, if it would be convex, $T$ would be the Delaunay triangulation. Simply speaking, the edge $(p_i,p_j)$ is an obstruction for the convexity of the surface, a concave edge. When flipping this edge we change the situation on the lifted surface only locally. So lets look at the 4 points $p_i,p_j,p_k,p_l$. In 3d they form a tetrahedron, that projects down to quadrilateral. Since the two triangles $p_ip_jp_k$ and $p_ip_jp_l$ define the the concave edge $(p_i,p_j)$, the triangles $p_kp_lp_i$ and $p_kp_lp_j$ define the a convex edge $(p_l,p_k)$. Therefore, flipping an illegal edge corresponds to replacing a concave edge by a convex edge in the lifting. Notice that this flips might turn other convex edges to concave edges.

Remark: The image is not geometrically correct and should only be considered as a sketch.

Let $T'$ be the triangulation after the flip. The lifted surface of $T'$ "contains" the surface of $T$. By this I mean that if you watch the two surfaces from the $xy$ plane you see only triangles from the surface of $T'$ (or triangles that are in both surfaces). You could also say that the surface of $T'$ encloses more volume. Also, the edge $(p_i,p_j)$ lies now "behind" the lifted surface induced by $T'$ when watching from the $xy$ plane.

During the flip sequence we get a sequence of surfaces with strictly increasing volume. Thus, the edge $(p_i,p_j)$ lies "behind" all these surfaces. Hence, it can never reappear during the flipping process. Since there are only $n$ choose 2 possible edges, we have at most $O(n^2)$ flips.