Voronoi diagram

A Voronoi diagram divides the plane among a set of points called sites: each site owns the region of points at least as close to it as to any other site. The picture is a window on the plane, and the shading inside a region is only for the eye. The blue probe is the centre of an empty circle that reaches to its nearest site. Here you can move sites and watch their neighbours’ regions change, grow every region from its site, see the Delaunay triangulation, and even the sites out towards a honeycomb.

The points at least as close to a site $p$ as to another site $q$ form a half-plane bounded by the perpendicular bisector of $pq$. The region of $p$ is the intersection of these half-planes, one for each other site, so it is convex. Only some of these bisectors become edges. The sites whose regions share an edge with that of $p$ are its neighbours, and the other half-planes already contain the whole region. The frame only ends the window, and a region reaches to infinity exactly when its site lies on the boundary of the convex hull of all the sites.

Where three or more regions meet, the corner is equally far from their sites, so it is the centre of a circle through them. That circle holds no site: a site inside it would be nearer to the corner than those sites, and the corner would belong to that site’s region instead. Usually exactly three regions meet at a corner. Four meet when exactly four sites lie on an empty circle, as on a square grid, which sites scattered at random almost never do.

Grow lets every site grow a disc at the same speed. Each point is reached first by its nearest site, so the fronts meet exactly along the edges. The inset shows the same growth from the side. Over each point it raises a height equal to the distance to the nearest site, the lowest of the cones $z = |x - s|$ standing on the sites; the ridges are the edges, and the growth is water rising. The last place flooded is the highest point of the landscape in the frame, the centre of the largest empty circle centred in the frame.

Triangulation joins two sites whenever their regions share an edge, and adds dashed diagonals where four or more sites share an empty circle, as on a square grid. Unless all the sites lie on one line, the result is the Delaunay triangulation. The circumcircle of each triangle is the empty circle about a corner.

Even out moves each site to the centroid of its region, cut to the frame, and makes the regions anew, round after round. This is Lloyd’s algorithm. The inset plots the mean squared distance from a point of the frame to its nearest site, divided by the frame’s area per site. No round can raise it. With the sites fixed, nearest-site regions make it smallest, and with the regions fixed, centroids do. The honeycomb line is a lower bound, the value for equal regular hexagons with the sites at their centres. From scattered sites the process stops at a nearby resting place, not a perfect honeycomb: pentagons and heptagons are usually left side by side, like dislocations in a crystal.

The diagram is named after Georgy Voronoy, who studied such divisions in any dimension in 1908, and the triangulation after Boris Delaunay, who described it in 1934.