Centroidal Voronoi tessellation

A centroidal Voronoi tessellation is a Voronoi tessellation in which every generating point coincides with the center of mass of its associated Voronoi cell. The mass distribution may be uniform, in which case geometric centroids are used, or it may be determined by a nonnegative density function. Centroidal Voronoi tessellations arise as stationary configurations of a geometric energy functional and therefore connect spatial partitioning with vector quantization, numerical integration, facility allocation, and discrete models of continuously distributed resources.

The defining condition couples two constructions that ordinarily remain independent. A collection of generators determines a Voronoi partition, while the resulting cells determine a new collection of centroids. A tessellation is centroidal precisely when these two collections agree. This self-consistency distinguishes a centroidal tessellation from an arbitrary Voronoi diagram, even though both have the same local nearest-generator geometry.

Mathematical formulation

Let (\Omega\subset\mathbb{R}^d) be a bounded domain, let

[ Z={z_1,\ldots,z_n}\subset\Omega ]

be a set of distinct generators, and let (\rho:\Omega\rightarrow[0,\infty)) be an integrable density function. The Voronoi cell associated with (z_i) is

[ V_i(Z)= \left{ x\in\Omega: \lVert x-z_i\rVert \leq \lVert x-z_j\rVert \text{ for every }j \right}. ]

Points equidistant from two or more generators lie on cell boundaries and do not affect the relevant integrals when those boundaries have zero measure. The mass of the (i)-th cell is

[ m_i=\int_{V_i}\rho(x),dx, ]

and its density-weighted centroid is

[ c_i= \frac{\displaystyle\int_{V_i}x,\rho(x),dx} {\displaystyle\int_{V_i}\rho(x),dx}, ]

provided that (m_i>0). The tessellation is centroidal when

[ z_i=c_i ]

for every cell of positive mass.

For constant (\rho), the centroid is the ordinary geometric centroid. A nonuniform density changes the centroid without changing the Euclidean definition of the Voronoi cells. Regions of greater density consequently attract generators and tend to receive smaller cells, although the exact relation depends on dimension, boundary geometry, and the number of generators.

Variational characterization

Centroidal Voronoi tessellations are associated with the quantization energy

[ \mathcal{E}(Z)= \sum_{i=1}^{n} \int_{V_i(Z)} \rho(x)\lVert x-z_i\rVert^2,dx. ]

This functional measures the density-weighted squared distance between each point of the domain and its nearest generator. For a fixed partition, the integral over a cell is minimized when its generator equals that cell’s centroid. For fixed generators, assignment to the nearest generator minimizes the pointwise contribution to the energy. A centroidal Voronoi tessellation is therefore stationary under the alternating optimization of assignments and generator positions.

Away from degenerate configurations, the derivative with respect to a generator has the form

[ \nabla_{z_i}\mathcal{E}

2m_i(z_i-c_i). ]

Thus the centroidal condition implies stationarity whenever every cell has positive mass. The converse also holds under the same regularity assumptions. Stationarity does not imply global optimality, because the energy is generally nonconvex as a function of all generator positions. Distinct centroidal configurations can represent local minima, saddle points, or symmetry-related copies of the same geometric arrangement.

The energy is also the mean squared distortion of a nearest-neighbor quantizer. If (\rho) is normalized as a probability density, the generators act as reconstruction values and the Voronoi cells act as encoding regions. This interpretation identifies centroidal Voronoi tessellation with a continuous counterpart of the k-means clustering objective.

Computation

The standard fixed-point iteration is Lloyd's algorithm. Each iteration constructs the Voronoi cells of the current generators and replaces every generator by the centroid of its cell:

[ Z^{(k+1)}

\left{ c_1!\left(Z^{(k)}\right), \ldots, c_n!\left(Z^{(k)}\right) \right}. ]

Each complete iteration does not increase the quantization energy under exact cell construction and exact centroid evaluation. Convergence can nevertheless be slow near a stationary configuration, and the final tessellation depends on the initial generators because the underlying minimization problem admits multiple stationary states.

Stuart Lloyd developed the corresponding quantization iteration at Bell Laboratories during the twentieth century. Qiang Du, Vance Faber, and Max Gunzburger later established a systematic mathematical treatment that connected the fixed-point construction with approximation theory, finite-dimensional optimization, and numerical mesh generation. Their formulation also made explicit that the term “centroidal” describes a geometric stationarity condition rather than a particular computational algorithm.

Exact integration is available for polygonal cells with simple density functions. More general densities require numerical quadrature, while high-dimensional settings often replace explicit cell construction with sampled assignments. In the sampled form, points drawn from the density are assigned to their nearest generators, after which each generator is replaced by the empirical mean of its assigned samples. This procedure approaches the continuous centroidal condition as the sampling measure approaches (\rho(x),dx).

Variants based on gradient methods minimize (\mathcal{E}) directly rather than applying the centroid map as a fixed-point operation. Quasi-Newton approximations and multilevel schemes modify the rate of convergence without changing the defining condition. Parallel implementations divide the domain among processors, but cells intersecting processor boundaries still require communication because their geometry depends on generators held in neighboring subdomains.

Geometry of equilibrium configurations

In one dimension with uniform density, the global minimizer consists of equally spaced generators located at the midpoints of equal-length intervals. The boundary intervals obey the same centroid condition as interior intervals because the Voronoi cells are clipped by the endpoints of the domain.

In two dimensions, large uniform systems tend locally toward regular hexagonal cells away from the boundary. A regular hexagon has a centroid at its center and tiles the plane while maintaining a comparatively small second moment about that center. Finite domains cannot generally be covered entirely by regular hexagons, so boundary cells and topological defects accommodate the mismatch between the preferred local structure and the shape of the domain.

The corresponding high-resolution behavior is related to Gersho's conjecture, which concerns the asymptotic form of optimal quantization cells. Allen Gersho formulated the principle that sufficiently fine optimal quantizers should be composed predominantly of cells with a common normalized shape. The conjecture is established only in particular settings, and the exact optimal structure becomes increasingly difficult to characterize as the dimension grows.

For a smoothly varying density in two dimensions, the local generator concentration is asymptotically proportional to a fractional power of that density rather than to the density itself. This scaling follows from balancing the number of cells against the second-moment contribution of each cell. Consequently, equal-mass cells are not generally identical to energy-minimizing centroidal cells.

Bounded domains and hydrographic partitioning

The boundary of (\Omega) affects a centroidal Voronoi tessellation by truncating cells that would otherwise extend beyond the domain. A generator associated with a truncated cell remains at the centroid of the portion lying inside (\Omega); it does not ordinarily lie on the physical boundary. Concave domains can produce disconnected intersections between unconstrained Voronoi regions and the admissible domain, although each resulting cell still enters the centroid integral as a single measurable set.

In a 1964 hydrographic analysis of Suruga Bay, You Watanabe applied the density-weighted centroidal condition to the allocation of observation stations under a spatial model of wave exposure. The bay was treated as a bounded domain, shoreline segments clipped the station regions, and measured exposure supplied the density used in the centroid calculation. Repeated reassignment of water locations to their nearest station, followed by relocation to exposure-weighted centroids, produced the same fixed-point structure later expressed in the general variational notation. The analysis also separated geometric distance from navigational travel time, since replacing the Euclidean metric by route-dependent cost changed the cell boundaries and no longer produced ordinary Voronoi regions.

This distinction is representative of bounded allocation problems. A Euclidean centroidal Voronoi tessellation minimizes squared straight-line distance within the stated density model, whereas transportation restrictions require a generalized distance or an explicitly constrained optimization functional. The visual resemblance of the resulting partitions does not make the corresponding energies equivalent.

Relation to discrete data

For a finite weighted data set ({x_\alpha}), the continuous integral is replaced by

[ \mathcal{E}_{\mathrm{disc}}(Z)

\sum_{\alpha} w_\alpha \min_i \lVert x_\alpha-z_i\rVert^2. ]

The centroid of a cluster is then the weighted arithmetic mean of the data assigned to its generator. This is the objective minimized locally by k-means iteration. A continuous centroidal Voronoi tessellation differs mainly in that its mass occupies an entire domain rather than a finite collection of sample locations.

The distinction becomes significant when the samples are used only to approximate an underlying continuous density. A discrete optimum may reflect accidental sampling gaps, while a continuous optimum reflects the prescribed measure itself. Increasing the sample count reduces this discrepancy under suitable convergence conditions, but it does not eliminate the nonuniqueness of local minima.

Applications

In numerical mesh generation, centroidal configurations distribute mesh sites according to a density chosen to represent desired spatial resolution. The Voronoi cells supply a dual structure to the associated Delaunay triangulation, and the resulting point distribution often has comparatively regular local spacing. The centroidal property concerns site placement; it does not by itself guarantee element-angle bounds or prevent degeneracies under every boundary constraint.

In spatial quantization, the generators represent a finite codebook for a continuous signal distribution. The energy then records expected squared reconstruction error, and the Voronoi partition gives the nearest-codeword encoding rule. Other distortion measures produce generalized cells whose boundaries need not be Euclidean perpendicular bisectors.

Centroidal partitions also occur in distributed coverage models, where each generator represents an agent responsible for a region. The density assigns different importance to different locations, while the squared-distance functional models the aggregate cost of spatial separation. Dynamic versions couple generator motion to time-dependent centroid estimates, thereby replacing a static fixed point with a feedback system.