Centroidal Voronoi tessellation

Three centroidal Voronoi tessellations of five points in a square

In geometry, 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 (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 for K-means clustering or Quasi-Newton methods like BFGS. ^[1]

^ Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. Springer Series in Operations Research and Financial Engineering (second ed.). Springer. doi:10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.

[1] Nocedal, Jorge; Wright, Stephen J. (2006). Numerical Optimization. Springer Series in Operations Research and Financial Engineering (second ed.). Springer. doi:10.1007/978-0-387-40065-5. ISBN 978-0-387-30303-1.

[1]