Lloyd's Relaxation: Combing Chaos Into a Honeycomb

Start with a Voronoi diagram

Scatter a set of points across a plane and ask, for every location, which point is closest - the answer partitions the plane into regions called Voronoi cells, one per point, and the whole partition is the Voronoi diagram. Random points produce a Voronoi diagram of wildly uneven cells: some tiny and crowded, others huge and empty, because nothing about random placement discourages clumping. Stuart Lloyd, working at Bell Labs in 1957 on a problem in signal quantisation, found a remarkably simple procedure that turns this uneven mess into something close to uniform.

The relaxation step: move to the centroid

Lloyd's algorithm alternates two operations. First, build the Voronoi diagram for the current points. Second, replace each point with the centroid (centre of mass) of its own cell rather than its original location. Repeat. Each pass nudges every point toward the middle of the region it currently controls - a point sitting in a cell that bulges to one side gets pulled toward that bulge, which shrinks the imbalance for next time.

repeat for N iterations:
  V = VoronoiDiagram(points)              // one cell per point
  for each point p, with cell C in V:
    p ← centroid(C)                        // area-weighted centre of mass

energy being minimised:
  E = Σ over cells ∫∫_C |x − centroid(C)|² dA

Why energy falls every single pass

The process can be understood as gradient descent on a specific quantity: the sum, over every cell, of the squared distance from each point inside the cell to that cell's own centroid. Moving a cell's generating point to its centroid is provably the choice that minimises that cell's own contribution to the total, holding the cell boundaries fixed - so each Lloyd step can only decrease or hold constant the overall energy, never increase it. That monotone decrease is what guarantees the process settles down rather than oscillating or diverging, even though it has no notion of a step size or learning rate the way gradient descent normally does.

The fixed point: a centroidal Voronoi tessellation

The process stops changing anything once every point already sits exactly at its own cell's centroid - moving it there again is a no-op. That configuration is called a centroidal Voronoi tessellation (CVT), and it is the fixed point Lloyd's algorithm converges toward. A perfect hexagonal grid is the most famous example of a CVT with identical cells, and it is not a coincidence that relaxed point sets tend to look hexagonal in the interior, away from any boundary: the regular hexagon is provably the most efficient way to partition the plane into equal-area, compact regions, minimising exactly the kind of squared-distance energy Lloyd's algorithm descends.

Where relaxed point sets actually get used

Lloyd relaxation shows up anywhere a set of sample points needs to be spread out evenly without an obvious grid structure. Mesh generation for finite-element simulation uses it to avoid the long, thin, numerically unstable triangles that come from unrelaxed random sampling. Stippling and dithering algorithms use it to place dots so that local density mimics an image's grey-scale value while avoiding the visually distracting clumps and voids of pure randomness - the technique underlies the popular "weighted Voronoi stippling" method for generating stipple-art from photographs. Blue-noise sample generation for rendering and procedural texture placement leans on the same idea: relaxed points still look organic and irregular, but without the clustering artefacts that plague naive random placement.

Frequently asked questions

Try it live

Everything above runs in your browser — open Lloyd's Relaxation and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.