In a Voronoi diagram, each region is determined by proximity to its generating site. An optimal arrangement is one in which every site best represents the spatial distribution of its region. This is achieved when each site lies exactly at the geometric center, or centroid, of its corresponding cell. In this configuration, the overall distance between each site and all the points in its region is minimized.
A centroidal Voronoi diagram (CVD) embodies this ideal of optimal site placement. In a CVD, every site is precisely located at the centroid of its Voronoi cell. This optimal state is attained by minimizing a natural geometric measure— the energy functional—which quantifies the total discrepancy between the sites and the true centers of their regions. The energy functional is defined as:
where \(V(p_i)\) denotes the Voronoi cell associated with site \(p_i\). A centroidal arrangement represents a stable, balanced configuration—one that is both mathematically elegant and visually appealing.
A straightforward yet powerful method for constructing a centroidal Voronoi diagram is known as Lloyd's algorithm. At its core, this elegant iterative approach continuously refines the sites of a Voronoi diagram by moving each one toward the centroid of its respective cell. With every iteration, the algorithm reduces the energy functional that quantifies the system’s imbalance, gradually nudging the configuration toward a more optimal and stable state.
|
The interactive diagram below shows the steps of Lloyds's algorithm as it constructs a CVD. Advance
incrementally through each step or run the algorithm in real time.
|
|
Sites
Energy
|
Lloyd's algorithm is guaranteed to converge to a local minimum in the energy landscape. The journey to reach these stable states isn’t always quick or smooth, however. Energy plateaus and false floors pepper the space with "almost CVDs" that fall apart as gracefully as they come together. Despite these anomalies, a centroidal Voronoi diagram is always created in the end—and if its boundary is a regular convex polygon, that CVD, by definition, is a Rosette.