Matpic
mathematics, in pictures
Concept

Voronoi diagram

The division of a space into one region per site, each holding the points closer to that site than to any other. Every boundary is a bisector, so the regions are convex polygons, and the diagram answers which source got here first.

Named by 5 essays across one field — each of them below, with the objects they name alongside it.

The plane divided by nearest neighbour. 10 sites, and every point of the rectangle shaded by which site is closest to it. The boundaries are the places where two sites tie.

The plane, divided by whoever is nearest

Scatter some points and colour every other point of the plane by which one is closest. The result is a tiling nobody designed, and its dual triangulation has a property that no part of the construction mentions.

geometry · Voronoi The triangulation as the underside of a hull. Eight points on a floor, lifted onto a paraboloid above them. The faces of the lifted set's lower convex hull are shaded, and their shadows on the floor are the Delaunay triangulation of the original points.

One dimension up, and the circles disappear

The Delaunay triangulation is defined by a condition about circles, which is awkward to compute and awkward to reason about. Lift every point onto a paraboloid and the circles turn into planes, the condition turns into convexity, and a two-dimensional problem is solved by looking at a three-dimensional shape from underneath.

geometry · Voronoi A scatter walking towards its own centres. 4 panels of the same 24 sites: the initial clumpy scatter and the Voronoi diagram after 1, 3, 12 rounds of Lloyd's iteration, with the cost falling to 52% of the scatter's as the cells even out.

Every site in the middle of its own cell

Move each point to the centre of mass of its own Voronoi cell, then redraw the diagram, then do it again. The rule is two lines long, it never mentions hexagons, and what it settles into is a honeycomb.

geometry · Voronoi The diagram when the sites are not the same size. 7 weighted sites drawn as circles of different radius, with the power diagram over them. The boundaries are straight, as in the unweighted diagram, but each one is pushed towards the smaller of the two circles it separates.

When the sites are not the same size

Give every site a weight and the boundaries slide. The cells stay convex and the edges stay straight, which is surprising, and one thing happens that the unweighted diagram never allows — a site can end up owning nothing at all.

geometry · Voronoi The shortest tree was already in the triangulation. The Delaunay triangulation of 20 sites in faint lines with the minimum spanning tree drawn over it in heavy ones. Every tree edge is a triangulation edge, and the circles on the longest few tree edges as diameters contain no other site.

The tree inside the triangulation

The shortest network joining a set of points is built from edges chosen by length, and the triangulation is built from edges chosen by an emptiness condition about circles. The two constructions share no step, and every edge of the first is an edge of the second.

geometry · Voronoi

Named alongside it

The objects these essays reach for when they reach for this one.

ConvexityDelaunay triangulationDualityCircleCircumcircleConvex hullLifting mapPlanar graphCentroidComplexityEuler characteristicFixed point

All concepts