**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Centroidal Voronoi tessellation

Summary

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.
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 to a basic cell which depends on the dimension."
In two dimensions, the basic cell for the optimal CVT is a regular hexagon 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.
Centroidal Voronoi tessellations are useful in data 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 image can be used as a density function to weight the points of a CVT, as a way to create digital stippling.
Many patterns seen in nature are closely approximated by a centroidal Voronoi tessellation. Examples of this include the Giant's Causeway, the cells of the cornea, and the breeding pits of the male tilapia.

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (3)

Related people (9)

Related courses (1)

Related publications (34)

Related units (1)

Related lectures (13)

Voronoi diagram

In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation.

Vector quantization

Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by dividing a large set of points (vectors) into groups having approximately the same number of points closest to them. Each group is represented by its centroid point, as in k-means and some other clustering algorithms.

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 cluster centroid), serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells. k-means clustering minimizes within-cluster variances (squared Euclidean distances), but not regular Euclidean distances, which would be the more difficult Weber problem: the mean optimizes squared errors, whereas only the geometric median minimizes Euclidean distances.

MATH-504: Integer optimisation

The course aims to introduce the basic concepts and results of integer optimization with special emphasis on algorithmic problems on lattices that have proved to be important in theoretical computer s

Explores the closest vector problem in lattices and the role of Voronoi cells in determining the closest vector.

Explores the Closest Vector Problem and Voronoi cells in lattice reduction algorithms.

Covers global navigation, path planning algorithms, cell decomposition, potential field methods, and stigmergy-based path optimization.

Ludovic Righetti, Elham Daneshmand

In this paper, we propose a novel framework capable of generating various walking and running gaits for bipedal robots. The main goal is to relax the fixed center of mass (CoM) height assumption of the linear inverted pendulum model (LIPM) and generate a w ...

Mario Paolone, Christophe Nicolet, Elena Vagnoni, Martin Seydoux

The number of transient operations in hydraulic machinery connected to power grid, notably start-ups and shut-downs, has observed a substantial increase in recent decades, primarily driven by the global shift toward intermittent renewable energy sources. S ...

2024New fabrication technologies have significantly decreased the cost of fabrication of shapes with highly complex geometric structure. One important application of complex fine-scale geometric structures is to create variable effective elastic material prope ...