The lab
Voronoi diagrams
Click anywhere to add a site. Drag sites to move them. Each colored region contains every point that is closer to its site than to any other. The boundaries between regions are equidistant from two sites — they form the edges of the diagram.
Voronoi diagrams appear everywhere: cell territories in biology, service areas in logistics, crystal grain boundaries in materials science, the wing venation of dragonflies. Wherever space is partitioned by proximity, Voronoi is the shape it takes.
0 sites
The Delaunay triangulation (thin lines) is the dual of the Voronoi diagram: connect each pair of sites whose Voronoi regions share an edge. Delaunay triangulations maximize the minimum angle of all triangles — they avoid long, thin slivers. This property makes them the preferred mesh for finite element analysis and terrain rendering.
Lloyd's algorithm: repeatedly replace each site with the centroid of its Voronoi region, then recompute. Iterated, this produces a centroidal Voronoi tessellation — the most uniformly distributed arrangement of sites. Click "show centroids" to see where each site would move.