Voronoi Diagram & Delaunay Triangulation
Click to place sites and watch the nearest-neighbour partition appear instantly. Toggle the dual Delaunay triangulation, animate Lloyd’s relaxation to grow a Centroidal Voronoi Tessellation, and explore one of the most useful structures in computational geometry.
Keyboard: R random C clear L Lloyd step Space animate CVT | Click canvas to add site · click site dot to remove · drag to reposition
Understanding Voronoi Diagrams
A Voronoi diagram (or Thiessen polygon diagram) partitions the plane into n convex regions — one per site — where each region contains all points closer to its site than to any other. The structure appears everywhere in nature and engineering, from crystal grains and soap-bubble packings to territorial maps and mobile-phone cell towers.
🥷 Definition
For a finite point set S in the plane, the Voronoi cell of site pᵢ is V(pᵢ) = { x ∈ ℝ² : ‖x−pᵢ‖ ≤ ‖x−pⱼ‖ for all j≠i }. Each cell is the intersection of n−1 half-planes, making it a convex polygon. Voronoi cells for sites in general position have no two sites equidistant from more than one vertex.
🔎 Voronoi Vertex
A Voronoi vertex is equidistant from exactly three sites (in general position) — it is the circumcenter of a Delaunay triangle. The total number of vertices is at most 2n−5 and the total number of edges is at most 3n−6 for n sites, by Euler's formula for planar graphs.
⚡ Fortune's Algorithm
The fastest exact algorithm runs in O(n log n) time using a sweepline and a priority queue. The sweepline sweeps top-to-bottom; parabolas (equidistant sets from site and sweepline) form the beach front. Breakpoints between adjacent parabolas trace Voronoi edge segments.
🧮 This Simulator
This page uses the Bowyer-Watson incremental Delaunay algorithm (O(n²) worst case, O(n log n) average) and derives Voronoi edges as the dual: circumcenter-to-circumcenter line segments between adjacent triangles. Region colouring uses a pixel-by-pixel nearest-site pass with typed arrays.
Delaunay Triangulation
The Delaunay triangulation DT(S) is the unique triangulation of a point set where the circumcircle of every triangle contains no other site in its interior. It is the geometric dual of the Voronoi diagram — every Voronoi edge corresponds to a Delaunay edge between two adjacent sites.
⚪ Circumcircle Test
Triangle (a,b,c) is Delaunay if and only if the determinant det[a−d, b−d, c−d] where the matrix has columns (x, y, x²+y²) is negative for every other site d. This is equivalent to point d being outside the circumcircle through a, b, c.
🏆 Why Delaunay?
Among all triangulations of a point set, Delaunay maximizes the minimum angle of all triangles (the max-min-angle property). This produces "fat" triangles that are numerically stable for finite-element analysis, terrain modeling (TINs), and mesh generation in computational fluid dynamics.
🔄 Bowyer-Watson
The incremental algorithm adds one site at a time. For each new site p: (1) find all triangles whose circumcircle contains p; (2) delete them, forming a polygonal hole; (3) connect p to all boundary edges of the hole. Step 1 costs O(k) per insertion where k is the number of triangles deleted.
📜 Duality
Connect any two sites whose Voronoi cells share an edge → Delaunay triangulation. Conversely, connect the circumcenters of all adjacent Delaunay triangles → Voronoi diagram. The toggle in this simulator lets you see both dual structures simultaneously.
Lloyd’s Relaxation & Centroidal Voronoi Tessellation
Lloyd's algorithm (1982) iteratively moves each site to the centroid of its Voronoi cell, then reconstructs the diagram. Iterating to convergence produces a Centroidal Voronoi Tessellation (CVT), where every site equals the mass-centroid of its region.
🎨 Stippling
CVT produces optimally-spaced point distributions used in stippling (converting photos to dot patterns). Each dot placed at a Voronoi centroid produces perceptually uniform, aesthetically pleasing pointillist output. Click "Animate CVT" and load 100 random points to see convergence live.
🏗 Facility Location
The CVT solves the optimal facility placement problem: if you must place n fire stations, hospitals, or mobile towers to minimise the average travel distance from any point to its nearest facility, the CVT gives the optimal locations (under a uniform population density model).
🧭 Blue Noise
Random point sets have clustering artefacts (Poisson clumping). CVT produces blue-noise distributions — nearly uniform spatial density with no low-frequency clustering. Blue noise is used in graphics (anti-aliasing, ray-tracing sample distributions) and audio (dithering).
🧊 Hexagonal Limit
The CVT in 2D converges toward a hexagonal tiling — the most efficient 2D packing. Hexagons are the optimal Voronoi partition minimising perimeter for fixed area. This explains honeycomb structure in beehives, bubble rafts, and columnar basalt (Giant's Causeway) — nature finds the CVT through surface tension minimisation.
Key Equations & Properties
| Result | Formula | Meaning |
|---|---|---|
| Voronoi cell | V(pᵢ) = { x : ‖x−pᵢ‖ ≤ ‖x−pⱼ‖ ∀j≠i } | All points closest to site pᵢ |
| Complexity | Vertices ≤ 2n−5, Edges ≤ 3n−6 | Euler's formula for planar Voronoi (n ≥ 3) |
| Fortune's runtime | O(n log n) | Optimal for algebraic decision tree model |
| Delaunay circumcircle | det[a−d, b−d, c−d] < 0 for all d ≠ a,b,c | No fourth point inside circumcircle |
| Circumcenter | O = (|a|²(b−c) + |b|²(c−a) + |c|²(a−b)) / (2·det) | Equidistant from all three triangle vertices |
| CVT centroid | c = (1/A) ∫∫ x dA | Lloyd's target for each site |
| Hexagonal efficiency | A/P² = √3/12 ≈ 0.1443 | Hexagon maximises area/perimeter² ratio in 2D |
| Delaunay−Voronoi duality | DT = dual(VD) | Shared Voronoi edge ↔ Delaunay edge between sites |
Real-World Applications
🔬 Crystallography
Wigner-Seitz unit cells in solid-state physics are Voronoi cells of lattice points. The first Brillouin zone in reciprocal space is also a Voronoi cell. Crystal grain analysis uses Voronoi tessellations to model polycrystalline metal microstructures.
🧬 Cell Biology
Cell territory models use Voronoi regions to approximate cell boundaries from cell nucleus positions, useful in computational histology and tumour analysis. Voronoi diagrams have been used to study tumour microenvironments and predict cancer progression.
🌏 Geography
Thiessen polygons (Voronoi cells) assign weather station data to geographic areas, used in hydrology for precipitation estimation. John Snow's 1854 Broad Street cholera map is a historic example — the Voronoi cell of the contaminated pump contained most deaths.
📶 Telecommunications
Mobile phone cell coverage is modelled as Voronoi cells with base stations as sites. Frequency assignment, handover regions, and interference analysis all use Voronoi geometry. 5G small-cell network planning requires solving CVT-like placement problems.
💻 Computer Graphics
Procedural texture generation, breakable object fracture patterns, and stippling all use Voronoi diagrams. Shadow maps, ambient occlusion, and screen-space effects use Delaunay-based mesh decomposition for sampling distributions.
🛠 Mesh Generation
Finite-element and finite-volume solvers require high-quality triangular or tetrahedral meshes. Delaunay triangulation with Ruppert's or Chew's refinement algorithm produces meshes with guaranteed minimum angle bounds, critical for stable numerical PDEs.
Curriculum Alignment
| Level | Topic connection |
|---|---|
| GCSE / IGCSE | Loci and regions — "all points equidistant from two fixed points form the perpendicular bisector"; Voronoi is the 3+ source generalisation |
| A-Level Further Mathematics | Graph theory, planar graphs (Euler formula V−E+F=2), computational problems, complex number geometry |
| A-Level Computer Science | Algorithm complexity O(n log n), divide-and-conquer, data structures (priority queue, BST), graph algorithms |
| IB Maths AA / AI HL | Graph problems, geometric transformations, probability distributions, optimisation |
| AP Computer Science A | Algorithm design, spatial data structures, geometric algorithms |
| University (Year 1–2) | Computational geometry (CS), solid-state physics (Wigner-Seitz cells), numerical methods (FEM mesh generation) |
| University (Year 3+) | Geometric measure theory, digital topology, probabilistic geometry, stochastic geometry (random CVTs) |
Worked Example: 3-Site Voronoi by Hand
Problem
Given sites A = (2,4), B = (6,2), C = (5,7), find the Voronoi vertex (circumcenter of the Delaunay triangle ABC).
Step 1 — Perpendicular bisector of AB: midpoint M_AB = (4,3); slope AB = −½ → perp slope = 2 → bisector: y−3 = 2(x−4) → y = 2x−5.
Step 2 — Perpendicular bisector of BC: midpoint M_BC = (5.5,4.5); slope BC = 5 → perp slope = −⅕ → bisector: y−4.5 = −⅕(x−5.5) → y = −x/5 + 5.6.
Step 3 — Solve simultaneously: 2x−5 = −x/5 + 5.6 → 2x + x/5 = 10.6 → (11x/5) = 10.6 → x = 4.82, y = 4.64.
Result — Voronoi vertex (circumcenter) ≈ (4.82, 4.64). Every point on the three bisectors is equidistant from two sites; the circumcenter is equidistant from all three. The Voronoi diagram consists of three regions separated by the three half-bisectors meeting at this vertex.
Frequently Asked Questions
What is a Voronoi diagram?
A Voronoi diagram partitions the plane into n regions — one per site — where each region contains all points closer to that site than to any other. Named after Georgy Voronyi (1868–1908), it arises in crystallography (Wigner-Seitz cells), biology (cell territories), geography (weather station catchments), and computer graphics. Given n sites, the diagram has at most 2n−5 vertices and 3n−6 edges, computable 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 is the unique triangulation of a point set where no point lies inside the circumcircle of any triangle. It is the geometric dual of the Voronoi diagram: connect any two sites sharing a Voronoi edge to get a Delaunay edge. 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 algorithm moves each site to the centroid of its Voronoi cell, then reconstructs the diagram. Iterating to convergence gives a Centroidal Voronoi Tessellation (CVT) — where every site equals the mass-centroid of its region. CVTs produce optimally uniform point distributions, analogous to beehive hexagonal cells that minimise wax per unit area. Applications: stippling, blue-noise sampling, optimal facility placement, mesh smoothing.
Where are Voronoi diagrams used in real life?
They appear across science and engineering: crystallography (unit cells), cell biology (territory models), geography (Thiessen polygons, precipitation maps), urban planning (optimal service placement), mobile networks (cell tower coverage), computer graphics (procedural textures, fracture simulations), and epidemiology (John Snow's 1854 cholera map).
Related Simulations
Graph search algorithms on grids.
Mandelbrot FractalIterative complex-plane geometry.
Flocking / BoidsSpatial neighbourhood rules.
Lorenz AttractorStrange attractors in 3D phase space.
Related Articles
- Voronoi Diagrams & Computational Geometry — blog article
- Graph Theory & Network Mathematics — blog article
- Chaos Theory & the Double Pendulum — blog article
📐 Explore 34 Interactive Simulations
Gain full access to all 34 simulations — including fluid dynamics, neural networks, orbital gravity, quantum mechanics, and more — with a Premium subscription.
View Pricing →