In geometry

Geometry

Geometry arose as the field of knowledge dealing with spatial relationships. Geometry was one of the two fields of pre-modern mathematics, the other being the study of numbers ....

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

Voronoi diagram

In mathematics, a Voronoi diagram is a special kind of decomposition of a given space, e.g., a metric space, determined by distances to a specified family of objects in the space...

s. A Voronoi tessellation is called centroidal when the generating point of each Voronoi cell is also its mean (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

Lloyd's algorithm

In computer science and electrical engineering, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm for grouping data points into a given number of categories, used for k-means clustering....

 for K-means clustering.

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

Congruence (geometry)

In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...

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

Centroidal Voronoi tessellations are useful in data compression

Data compression

In computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....

, optimal quadrature

Numerical integration

In numerical analysis, numerical integration constitutes a broad family of algorithms for calculating the numerical value of a definite integral, and by extension, the term is also sometimes used to describe the numerical solution of differential equations. This article focuses on calculation of...

, optimal quantization

Quantization (signal processing)

Quantization, in mathematics and digital signal processing, is the process of mapping a large set of input values to a smaller set – such as rounding values to some unit of precision. A device or algorithmic function that performs quantization is called a quantizer. The error introduced by...

, clustering

Data clustering

Cluster analysis or clustering is the task of assigning a set of objects into groups so that the objects in the same cluster are more similar to each other than to those in other clusters....

, and optimal mesh generation. Many patterns seen in nature are closely approximated by a Centroidal Voronoi tesselation. Examples of this include the Giant's Causeway

Giant's Causeway

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

, the cells of the cornea

Cornea

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

, and the breeding pits of the male tilapia

Tilapia

Tilapia , is the common name for nearly a hundred species of cichlid fish from the tilapiine cichlid tribe. Tilapia inhabit a variety of fresh water habitats, including shallow streams, ponds, rivers and lakes. Historically, they have been of major importance in artisan fishing in Africa and the...

.