What is a Voronoi diagram?

A Voronoi diagram partitions a plane into regions based on distance to a set of seed points called sites. Each region consists of all points closer to its site than to any other. Named after Ukrainian mathematician Georgy Voronyi (1868–1908), it appears in crystallography (Wigner-Seitz cells), cellular biology (cell territory), geography (catchment areas), and computer graphics. Given n sites, the diagram has at most 2n−5 Voronoi vertices and 3n−6 edges, and is computed in O(n log n) time via Fortune's sweepline algorithm.

What is the Delaunay triangulation and how does it relate to Voronoi diagrams?

The Delaunay triangulation of a point set is the unique triangulation (for points in general position) where no point lies inside the circumcircle of any triangle. It is the geometric dual of the Voronoi diagram: draw a line segment through each shared Voronoi edge between two adjacent regions, connecting their respective sites — this is the Delaunay triangulation. Delaunay triangulations maximise the minimum angle of all triangles, making them ideal for finite-element mesh generation, terrain modelling, and computational physics.

What is Lloyd's relaxation and what is a Centroidal Voronoi Tessellation?

Lloyd's relaxation is an iterative algorithm that moves each site to the centroid of its Voronoi cell, then recomputes the Voronoi diagram. Repeated iterations converge to a Centroidal Voronoi Tessellation (CVT) — a special configuration where each site exactly coincides with the centroid of its region. CVTs produce exceptionally uniform, optimally-distributed point patterns used in stippling (pointillist art), blue-noise sampling (computer graphics), mesh smoothing, and optimal facility placement (locating hospitals, warehouses, mobile phone towers).

Where are Voronoi diagrams used in real life?

Voronoi diagrams appear across science and engineering: (1) Crystallography — Wigner-Seitz cells in solid-state physics are Voronoi cells around atomic lattice points. (2) Biology — territorial regions of animals, proximity models for cell growth, plant competition for light. (3) Geography — Thiessen polygons identifying nearest meteorological station for each location. (4) Urban planning — optimal placement of services (hospitals, schools, fire stations). (5) Computer graphics — procedural texture generation, stippling, screen-space ambient occlusion. (6) Epidemiology — Voronoi catchment areas to assign patients to nearest GP surgery (John Snow's 1854 Broad Street cholera map is an early example).

Home▸Mathematics▸Voronoi Diagrams & Delaunay Triangulation

🧪 Voronoi Diagrams & Delaunay Triangulation

Interactive Voronoi diagram and Delaunay triangulation simulator. Click to place sites, drag to move. Toggle between Voronoi regions, Delaunay edges, and circumcenters. Animate Lloyd's relaxation to compute Centroidal Voronoi Tessellation (CVT). Free browser-based computational geometry tool.

Mathematics2DModerate60 FPS

⚙ Under the hood

This simulation allows users to generate Voronoi diagrams and Delaunay triangulations. It provides an interactive exploration of these geometric concepts, showcasing how points are partitioned based on proximity.

Voronoi DiagramDelaunay TriangulationGeometric Algorithms

2D · HTML5 Canvas 2D · 60 FPS target · runs fully client-side, no install