What is Lloyd relaxation?
Lloyd relaxation, or Lloyd's algorithm, turns a random scatter of points into an even one. Each iteration builds the Voronoi diagram of the points and then moves every point to the centroid of its cell. Points crowded together have small cells and get pushed apart; points with big empty cells drift into the gap. After a handful of iterations the cells are nearly equal in size, and in the middle of the region they approach regular hexagons.
How to use the visualizer
- Choose a starting layout — uniform random, clustered, or bunched in the center — and the number of points.
- Press Play, or Step through one iteration at a time.
- The arrows show where each point will move next; they shrink as the diagram settles.
- The chart tracks cell size variation: it falls quickly in the first iterations, then levels off.
Centroidal Voronoi tessellations
When every point sits exactly at the centroid of its own cell, the diagram is a centroidal Voronoi tessellation (CVT). It is the layout that minimizes the average squared distance from any location to its nearest point, which is why CVTs appear in mesh generation, sensor and facility placement, image compression, stippling and procedural maps. Lloyd's algorithm is also the same idea as k-means clustering, applied to a continuous area instead of a set of data points.
See the technique at work in the Voronoi pattern generator (the Regularity slider) and in Voronoi stippling, which weights each centroid by image darkness.
Frequently asked questions
What is Lloyd's algorithm?
Lloyd's algorithm alternates two steps: build the Voronoi diagram of the current points, then move every point to the centroid (center of mass) of its cell. Repeating these steps spreads the points out evenly. It was described by Stuart Lloyd in 1957 for signal quantization and is closely related to k-means clustering.
What is a centroidal Voronoi tessellation?
A Voronoi diagram in which every site sits exactly at the centroid of its own cell. Lloyd's algorithm converges toward one. Inside a large region, the cells of a centroidal Voronoi tessellation tend toward regular hexagons.
What does the size variation number mean?
It is the coefficient of variation of the cell areas: the standard deviation divided by the mean. Random points usually start around 50 to 60 percent; after relaxation it typically drops below 10 percent.
How many iterations are needed?
Most of the change happens in the first five to ten iterations. After that points move only slightly; the animation stops by itself when the average movement falls below a twentieth of a pixel.