Voronoi Diagrams

What’s going on

A town has nine shops. You want milk, and you go to the nearest shop. Your neighbour does the same, and so does everyone else. Now colour every spot on the map by the shop its owner would walk to. The map breaks into patches, one for each shop. This picture is called a Voronoi diagram, and each patch is a cell.

Press Find my nearest shop in the scene and move the pointer around. The orange line always runs to the nearest shop, and the dashed line to the next nearest. Watch what happens when you cross a border: the two lines become equally long, and then they swap.

Two shops: a straight border

Start with just two shops, A and B. The points that are exactly as far from A as from B form a straight line. It passes through the middle of the segment AB and crosses it at a right angle. This line is called the perpendicular bisector of AB. Everything on A’s side of it is closer to A.

So every border in the diagram is a piece of a perpendicular bisector, and every cell has straight sides.

Many shops: cut, cut, cut

To build the cell of one shop, take its bisector with each of the other shops in turn, and each time keep only the half of the map on its side. What is left at the end is its cell. Tick Bisectors of the chosen shop to see all those cuts at once: most of them miss the cell entirely, and only the bisectors with the neighbouring shops make its sides.

This also explains why every cell is convex: it has no dents, because cutting with straight lines can never make one.

Click anywhere on the map to open a new shop. Only the cells next to it change; the rest of the town does not notice.

Corners and circles

Where three cells meet, the corner is equally far from three shops. So a circle centred at that corner passes through all three. Tick Circles through three shops: every circle has three shops on it and no shop inside it. If there were a shop inside, that shop would be closer to the corner, and the corner would belong to its cell instead.

Out in the world

The same pattern appears whenever things grow outwards from many centres at the same speed and stop where they meet. Picture ink dripping onto paper at many spots at once: each blot spreads until it bumps into its neighbours, and the boundaries are exactly the borders of a Voronoi diagram. Patterns very like this can be seen on the coat of a reticulated giraffe and in the network of veins in a dragonfly’s wing.

People use the diagrams on purpose too: to plan which school or fire station serves which streets, to place mobile phone masts, and to find the nearest object quickly in computer games and maps.

Try it yourself

1. Shops in a row

Five shops stand on one straight street, 100 m apart. What do their cells look like?

Answer

Strips. All the borders are perpendicular to the street, halfway between neighbouring shops, so they are parallel lines 100 m apart. The two end shops get everything beyond the last border. Try it: put shops in a line in the scene.

2. A wide triangle

Three shops make a triangle with one very wide angle, more than 90°. Where is the point that is equally far from all three?

Answer

Outside the triangle, beyond its longest side. It is still the centre of the circle through the three shops, and it is still where the three borders meet. For a right angle it sits exactly on the middle of the longest side; for a sharper triangle it is inside.

3. A shop closes

One shop closes. Which customers have to change shop, and where do they go?

Answer

Only the people in the closed shop's cell. They are shared among the shops whose cells were next to it, and the rest of the map stays the same. Press Remove shop to watch its cell be shared out.

Go deeper

• The diagrams are named after Georgy Voronoy, who studied them in 1908. Peter Gustav Lejeune Dirichlet had used them earlier, so they are also called Dirichlet tessellations.
• Join every pair of shops whose cells share a border, and you get a network of triangles called the Delaunay triangulation, after Boris Delaunay. It is used to build 3D models and maps from scattered measurements.
• In 1854 the doctor John Snow traced a cholera outbreak in London to one water pump. A map from his study marks the area that was closer to that pump than to any other, which is one cell of a Voronoi diagram, measured in walking distance.