geometry Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...

, a centroidal Voronoi tessellation (CVT) is a special type of

Voronoi tessellation Voronoi or Voronoy is a Slavic masculine surname; its feminine counterpart is Voronaya. It may refer to *Georgy Voronoy (1868–1908), Russian and Ukrainian mathematician **Voronoi diagram **Weighted Voronoi diagram ** Voronoi deformation density ** ...

in which the generating point of each Voronoi cell is also its

centroid In mathematics and physics, the centroid, also known as geometric center or center of figure, of a plane figure or solid figure is the arithmetic mean position of all the points in the surface of the figure. The same definition extends to any ob ...

(center of mass). It can be viewed as an optimal partition corresponding to an optimal distribution of generators. A number of algorithms can be used to generate centroidal Voronoi tessellations, including

Lloyd's algorithm In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of t ...

for

K-means clustering ''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster with the nearest mean (cluster centers or ...

Quasi-Newton method Quasi-Newton methods are methods used to either find zeroes or local maxima and minima of functions, as an alternative to Newton's method. They can be used if the Jacobian or Hessian is unavailable or is too expensive to compute at every iteration. ...

s like BFGS.

Proofs

Gersho's conjecture, proven for one and two dimensions, says that "asymptotically speaking, all cells of the optimal CVT, while forming a

tessellation A tessellation or tiling is the covering of a surface, often a plane (mathematics), plane, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to high-dimensional ...

, are

congruent Congruence may refer to: Mathematics * Congruence (geometry), being the same size and shape * Congruence or congruence relation, in abstract algebra, an equivalence relation on an algebraic structure that is compatible with the structure * In mod ...

to a basic cell which depends on the dimension." In two dimensions, the basic cell for the optimal CVT is a regular

hexagon In geometry, a hexagon (from Ancient Greek, Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple polygon, simple (non-self-intersecting) hexagon is 720°. Regular hexa ...

as it is proven to be the most dense packing of circles in 2D Euclidean space. Its three dimensional equivalent is the

rhombic dodecahedral honeycomb The rhombic dodecahedral honeycomb (also dodecahedrille) is a space-filling tessellation (or honeycomb) in Euclidean 3-space. It is the Voronoi diagram of the face-centered cubic sphere-packing, which has the densest possible packing of equal s ...

, derived from the most dense packing of spheres in 3D Euclidean space.

Applications

Centroidal Voronoi tessellations are useful in

data compression In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...

, optimal quadrature, optimal quantization, clustering, and optimal mesh generation.. A weighted centroidal Voronoi diagrams is a CVT in which each centroid is weighted according to a certain function. For example, a

grayscale In digital photography, computer-generated imagery, and colorimetry, a grayscale image is one in which the value of each pixel is a single sample representing only an ''amount'' of light; that is, it carries only intensity information. Graysca ...

image can be used as a density function to weight the points of a CVT, as a way to create digital

stippling Stippling is the creation of a pattern simulating varying degrees of solidity or shading by using small dots. Such a pattern may occur in nature and these effects are frequently emulated by artists. Art In printmaking, stipple engraving is ...

Occurrence in nature

Many patterns seen in nature are closely approximated by a centroidal Voronoi tessellation. Examples of this include the

Giant's Causeway The Giant's Causeway is an area of about 40,000 interlocking basalt columns, the result of an ancient volcanic fissure eruption. It is located in County Antrim on the north coast of Northern Ireland, about three miles (5 km) northeast of ...

, the cells of the

cornea The cornea is the transparent front part of the eye that covers the iris, pupil, and anterior chamber. Along with the anterior chamber and lens, the cornea refracts light, accounting for approximately two-thirds of the eye's total optical power ...

, and the breeding pits of the male

tilapia Tilapia ( ) is the common name for nearly a hundred species of cichlid fish from the coelotilapine, coptodonine, heterotilapine, oreochromine, pelmatolapiine, and tilapiine tribes (formerly all were "Tilapiini"), with the economically most ...

References

{{reflist Discrete geometry Geometric algorithms Diagrams