Regions of nearest site
Given a set of points called sites, the Voronoi diagram carves the plane into one region per site. A region is the set of all locations closer to its site than to any other. This single picture answers a flood of nearest neighbor questions at a glance.
Edges and vertices
The structure has a clean meaning:
- A Voronoi edge is the set of points equidistant from two sites, a piece of their perpendicular bisector.
- A Voronoi vertex is equidistant from three sites at once, where three regions meet.
- Every region is convex, since it is an intersection of half planes.
These rules make the diagram a planar graph whose total size grows only linearly with the number of sites, despite the rich structure.
How it is built and used
A common construction is Fortune's sweep, which moves a line across the plane while tracking a parabolic beach line so the diagram emerges in one efficient pass. Once built, the diagram supports fast nearest site queries, helps place facilities to serve customers, and underlies clustering and mesh generation. It is the natural companion to its dual, the Delaunay triangulation.
Key idea
A Voronoi diagram splits the plane into convex regions of nearest site, with edges equidistant from two sites and vertices from three.