Voronoi diagrams and Delaunay triangulation

A Voronoi diagram divides a plane among a set of points, giving each point the area of all places that are nearer to it than to any other point. The Delaunay triangulation joins every point to the points whose areas touch its own. The two are named after the mathematicians Georgy Voronoy (1868–1908) and Boris Delaunay (1890–1980), and each can be made from the other.^{1, 2, 3, 4}

The cells

Start with some points, called sites. For one site, take every other site in turn and draw the line exactly halfway between the two, at right angles to the line joining them (the perpendicular bisector). Everything on this site's side of that line is nearer to it. What is left after all the other sites have cut their half away is the site's Voronoi cell.¹ The image at the top and the sketch below are made exactly like this.

The idea is older than the name. Dirichlet used such cells in 1850 in a study of quadratic forms, and Alfred H. Thiessen used them in 1911 to estimate rainfall, which is why they are also called Thiessen polygons. Voronoy defined and studied the general case, in any number of dimensions, in 1908, the year he died.^1, 2

The triangles

Join each site to every site whose cell shares an edge with its own, and the plane is covered with triangles: the Delaunay triangulation, the "dual" of the Voronoi diagram.^1, 3 It has a simple test: the circle through the three corners of any triangle has no other site inside it. Of all the ways of joining the same points into triangles, it is the one whose smallest angle is as large as possible.³

Delaunay (in Russian Delone) gave a talk called "Sur la sphère vide", on the empty sphere, at the International Congress of Mathematicians in Toronto in 1924; Wikipedia dates his work on the triangulation from 1934.^3, 4

New drawing

Faster methods, and art

The method used here cuts every cell against every other site, so the work grows quickly with the number of sites. Fortune's algorithm builds the whole diagram in time proportional to n log n, and the Bowyer–Watson algorithm builds the Delaunay triangulation by adding one point at a time.^1, 3

In Lloyd's algorithm the sites are moved, again and again, to the centre of their own cells, which spreads them out evenly.¹ A weighted version of the idea, which places dots for drawings made only of points, is the subject of Weighted Voronoi stippling. For another way to spread points evenly, see Poisson disc sampling. See also Generative Art.