Triangulation: Brute Force Delaunay

The story so far: we have a point set we wish to triangulate, and in particular we wish to find the Delaunay triangulation. We also know that Delaunay traingulations are dual to Voronoi diagrams, and so in theory we can solve either problem to come up with the answer to the other. How can we get a computer do to this for us?

Of the two, I consider the Delaunay triangulation to be the more natural representation for a computer. The reason is that Voronoi diagrams, due to the distant Voronoi vertex property, could be arbitrarily large in size, which poses problems for finite-precision computers. Delaunay triangulations, in contrast, are always bounded by the convex hull of the input point set. In addition, the Delaunay edges always have both ends at finite vertices, while Voronoi diagrams have at least three edges that radiate out towards a point at infinity. Therefore, let us make a computer compute a Delaunay triangulation for us.

There is a trivial brute-force algorithm for Delaunay triangulation:

1. Generate a list of all potential triangles by taking triples of points from the point set. There are at most (N)(N-1)(N-2)/6 distinct triangles.^[1]
2. For each triangle, test whether any other points in the point set are inside its circumcircle. If there are any, throw away the triangle. Otherwise, keep the triangle.

Note: this algorithm does not include special case handling for four or more points lying on a common circle. It will also count any edge not on the convex hull twice.

This algorithm works, but like many brute-force algorithms, it is not good enough. If the input size is N, then there are O(N³) triples of points to consider, and for each triple, we have to compare it to the other N-3 points in the point set. This puts the algorithm's runtime at O(N⁴), or in layman's terms, "hella slow".^[2]

An insightful computer scientist by the name of Fortune was able to find an algorithm to solve this problem in O(N log N) time. In the next post, we will see how he did it. Until then, you could try to solve it yourself.

---

[1] This is the common 'combination' operator from finite mathematics – N! / [(N-K)! K!] – with K=3.

[2] Binary search is O(log N). Efficient sorting algorithms are O(N log N). Algorithms start to look sluggish once they hit O(N²). Even this slow brute-force algorithm is doing better than O(M^N) though, and if you end up with O(N!), you'd better get some coffee, because there's a good chance the universe will end before your algorithm terminates.