A Voronoi diagram partitions space so that every point is assigned to its nearest seed. The boundary between two cells is the set of points equidistant from both seeds. The result is a tessellation of convex polygons that tiles the plane with no gaps.
The dual of a Voronoi diagram is the Delaunay triangulation. Connect two seeds whenever their Voronoi cells share an edge. The result is a triangulation with the property that no point lies inside any triangle's circumcircle. This maximizes the minimum angle across all triangles, avoiding thin slivers.
This implementation uses the Bowyer-Watson algorithm to build the Delaunay triangulation incrementally. For each new point: find all triangles whose circumcircle contains it, remove them to create a polygonal hole, then re-triangulate the hole. The Voronoi vertices are the circumcenters of the resulting triangles.
Voronoi diagrams appear everywhere: cell biology (cell territories), geography (nearest facility maps), materials science (crystal grain boundaries), and computational geometry (mesh generation). They are also the foundation of Lloyd relaxation, which iteratively moves seeds to their cell centroids to create evenly-spaced distributions.
Wikipedia: Voronoi diagram