Why is the empty circumcircle property important?

A triangulation is Delaunay iff every triangle’s circumcircle contains no other site. That criterion maximizes the minimum angle among triangulations of the point set, which helps avoid skinny triangles in meshes.

How are Voronoi and Delaunay dual?

Each Delaunay edge corresponds to two neighboring Voronoi cells; Voronoi vertices sit at circumcenters of Delaunay triangles. Drawing one determines the combinatorial structure of the other.

What does Bowyer–Watson do when I add a point?

It finds triangles whose circumcircles contain the new site, removes them, and retriangulates the resulting polygonal hole to the new point — restoring the Delaunay property incrementally.

Delaunay & Voronoi

Bowyer–Watson triangulation and dual Voronoi tessellation; click to add seeds, drag to move.

About this model

Given seed points in the plane, the Voronoi tessellation assigns each location to the nearest seed, while the Delaunay triangulation connects seeds whose Voronoi cells share an edge — equivalently, triangles whose circumcircles are empty of other seeds. This simulator builds the triangulation with a Bowyer–Watson incremental algorithm and draws the dual Voronoi diagram. Click to add seeds and drag to move them; the mesh and cells update live. The model is planar Euclidean nearest-neighbor geometry without weighted Voronoi sites, constrained triangulations, or curved metrics. Add and drag points to see empty-circumcircle flips and cell boundaries reshape.

Who it's for: Computational geometry, mesh generation, GIS, and intermediate algorithms courses.

Key terms

Delaunay triangulation
Voronoi diagram
Bowyer–Watson
Circumcircle
Tessellation
Nearest neighbor

How it works

The Voronoi diagram of N seeds partitions the plane into cells of points closer to seed i than to any other. Its dual graph is the Delaunay triangulation: connect two seeds whenever their Voronoi cells share an edge. Delaunay maximises the minimum angle of all triangles (no other triangulation does as well) and has the empty-circumcircle property — toggle the option to verify that no other seed lies inside any circumcircle. Implemented with the Bowyer–Watson incremental algorithm.

Key equations

V(sᵢ) = { x : ‖x − sᵢ‖ ≤ ‖x − sⱼ‖ ∀ j }

Delaunay edge ⇔ V(sᵢ) and V(sⱼ) share an edge

empty-circle: no seed is strictly inside circumcircle of any triangle

Frequently asked questions

Why is the empty circumcircle property important?: A triangulation is Delaunay iff every triangle’s circumcircle contains no other site. That criterion maximizes the minimum angle among triangulations of the point set, which helps avoid skinny triangles in meshes.
How are Voronoi and Delaunay dual?: Each Delaunay edge corresponds to two neighboring Voronoi cells; Voronoi vertices sit at circumcenters of Delaunay triangles. Drawing one determines the combinatorial structure of the other.
What does Bowyer–Watson do when I add a point?: It finds triangles whose circumcircles contain the new site, removes them, and retriangulates the resulting polygonal hole to the new point — restoring the Delaunay property incrementally.

Continue with similar topics in this category — or all 85 in Math Visualization.

View category →

NewSchool

Convex Hull (Graham & QuickHull)

Launch Simulator

Click to add points, drag to move; Graham scan with step playback or QuickHull divide-by-farthest; compare vertex sets.

NewSchool

K-Means Clustering (Lloyd)

Launch Simulator

Click to add points, choose k, randomize centroids, then step Lloyd iterations (assign to nearest centroid, update means). Optional Gaussian-mixture demo; watch within-cluster SSE decrease.

NewSchool

Random Walk (2D / 3D Lattice)

Launch Simulator

Nearest-neighbor SRW on Z² or Z³: ensemble mean ⟨r²⟩ vs time with y = t reference, histogram of r² across walkers, and Monte Carlo first-return times (recurrent vs transient).

NewSchool

Sandpile (SOC)

Launch Simulator

BTW abelian model: add grains, ≥4 topples to neighbors; critical avalanches.

FeaturedSchool

Trigonometry Circle

Launch Simulator

Unit circle with live sin, cos, tan values as you drag.

FeaturedSchool

Fourier Series

Launch Simulator

Build waveforms from sine waves. Add harmonics one by one.

Delaunay & Voronoi

About this model

How it works

Key equations

Frequently asked questions

Related simulators

Convex Hull (Graham & QuickHull)

K-Means Clustering (Lloyd)

Random Walk (2D / 3D Lattice)

Sandpile (SOC)

Trigonometry Circle

Fourier Series

Delaunay & Voronoi

About this model

How it works

Key equations

Frequently asked questions