geometry Geometry (; ) is a branch of mathematics concerned with properties of space such as the distance, shape, size, and relative position of figures. Geometry is, along with arithmetic, one of the oldest branches of mathematics. A mathematician w ...

, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation 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 figure. The same definition extends to any object in n-d ...

(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 ...

for

K-means clustering ''k''-means clustering is a method of vector quantization, originally from signal processing, that aims to partition of a set, partition ''n'' observations into ''k'' clusters in which each observation belongs to the cluster (statistics), cluste ...

Quasi-Newton method In numerical analysis, a quasi-Newton method is an iterative numerical method used either to find zeroes or to find local maxima and minima of functions via an iterative recurrence formula much like the one for Newton's method, except using ap ...

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, using one or more geometric shapes, called ''tiles'', with no overlaps and no gaps. In mathematics, tessellation can be generalized to higher dimensions and a variety ...

, 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 modu ...

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 Greek , , meaning "six", and , , meaning "corner, angle") is a six-sided polygon. The total of the internal angles of any simple (non-self-intersecting) hexagon is 720°. Regular hexagon A regular hexagon is de ...

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, 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 compressi ...

, 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 greyscale (more common in Commonwealth English) or grayscale (more common in American English) image is one in which the value of each pixel is a single sample (signal), s ...

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 Grayscale, 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 ...

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 approximately 40,000 interlocking basalt columns, the result of an ancient volcano, volcanic fissure eruption, part of the North Atlantic Igneous Province active in the region during the Paleogene period. ...

, the cells of the

cornea The cornea is the transparency (optics), transparent front part of the eyeball which covers the Iris (anatomy), iris, pupil, and Anterior chamber of eyeball, anterior chamber. Along with the anterior chamber and Lens (anatomy), lens, the cornea ...

, 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 mos ...

References

{{reflist Discrete geometry Geometric algorithms Diagrams