Hello everyone! Recently I wanted to solve the problem 102482G - Panda Preserve, and I couldn’t find a simple implementation of Delaunay triangulation anywhere.

In this blog I want to talk about what a Delaunay triangulation is, what a Voronoi diagram is, how they are related, and how they can be constructed without using complex data structures.

Let’s begin with several definitions and facts:

A triangulation is a partition of some set of points S into triangles such that the interior regions of the triangles do not intersect.

A Delaunay triangulation is such a partition of a set of points S into triangles that inside the circumcircle of each triangle there are no points from the set.

A Voronoi diagram is a partition of the plane in which each region consists of points that are closer to one element of the set S than to any other element.

The Voronoi diagram and the Delaunay triangulation are dual graphs .

Delaunay triangulation construction algorithm in $$$O(n^2)$$$

First of all, it’s worth mentioning that the Delaunay triangulation can be constructed much faster than in $$$O(n^2)$$$. You can read more about this тут . However, the Fortune algorithm presented there is too difficult to understand and writing it during a contest is extremely hard.

The $$$O(n^2)$$$ implementation is quite simple in terms of ideas and consists of 2 steps.

Step 1

We construct an arbitrary triangulation of the given set of points. This construction is similar to constructing a convex hull. Among all points of the set, we find the point with the smallest x-coordinate, and if there are several, then the one with the smallest y-coordinate. Let this point be P. Shift all coordinates so that point p ends up at the origin. Compute the polar angles of all points relative to p to sort them around it.

We will build the triangulation in 2 phases:

In the first phase, we connect all points with point p and also connect neighboring points with each other. If it were guaranteed that the initial set of points forms a convex polygon, this would already be sufficient, but this is not guaranteed.

In the second phase, we act similarly to the algorithm of Грэхема for constructing the convex hull. Each time we add a new point, we must check whether the convexity condition is violated. If it is violated, then we have found a “dent” that must be filled.

In this example, when attempting to add vertex 3 to the convex hull, it turns out that the convexity condition is violated, and triangle 123 must be added to the triangulation.

Step 2

We already have some triangulation of the set of points, but it does not yet satisfy the criteria of a Delaunay triangulation. We will iteratively improve our triangulation. At each step, we search for a quadrilateral ABCD such that it contains the edge AC, and triangles ABC and ACD do not satisfy the Delaunay criterion. The flip operation removes edge AC and adds edge BD. For example, if initially we had triangles ABC and ACD, then after applying the operation we get triangles ABD and BCD. It can be proven that if the initial partition does not satisfy the Delaunay criterion, then a flip fixes this. For brevity, I will not give this proof here. This process repeats until all edges satisfy the Delaunay criterion.

Example of the flip operation.

Connection with the Voronoi diagram

In fact, having the Delaunay triangulation, building the Voronoi diagram is very easy. For each triangle, find the center of its circumcircle, connect the centers of circumcircles of adjacent triangles, and draw rays to infinity for those triangles that have no neighbors.

Connection between the Voronoi diagram and the Delaunay triangulation (black lines — Delaunay triangulation, red lines — Voronoi diagram).

Generalization

The iterative flip algorithm runs in $$$O(n^2)$$$ in the worst case, because in the worst case up to $$$O(n)$$$ flip operations may be required for each of the $$$O(n)$$$ edges that can undergo a flip. As already mentioned, there exist much faster and more precise ways to find the Delaunay triangulation, but this algorithm is simpler to understand and can be written in 30–40 minutes.

Here I provide the implementation of the algorithm, although, even though this code passed all tests of 102482G - Panda Preserve, if I were the reader I would still write it myself.

Tool, where you can visualize different triangulations produced by this code.

If you have any corrections or additions, write them in the comments.