Lloyd’s Relaxation


Lloyd’s relaxation algorithm generates a centroidal Voronoi tessellation, which is where the seed point for each Voronoi region is also its centroid.

The algorithm computes the Voronoi diagram for a set of points, moves each point towards the centroid of its Voronoi region, and repeats.

A modification of Lloyd’s relaxation algorithm can be used to generate a Voronoi treemap.