Carving up the plane
Given a set of sites, the Voronoi diagram partitions the plane so that every location belongs to the region of its nearest site. It is the canonical structure for proximity questions.
The structure of cells
Each site owns a convex Voronoi cell containing all points closer to it than to any other site.
- The boundary between two cells lies on the perpendicular bisector of their sites.
- A boundary edge holds points equidistant from two sites.
- A vertex is equidistant from three or more sites.
What it answers
The diagram makes many queries fast once built.
- Nearest site for any query point reduces to locating its cell.
- The largest empty circle centered among the sites sits at a Voronoi vertex.
- It reveals natural clustering and neighbor relationships.
Building it
Fortune sweep line method constructs the whole diagram in one elegant pass using a moving beach line of parabolic arcs. The diagram is the geometric dual of the Delaunay triangulation, so one can be derived from the other.
Key idea
A Voronoi diagram splits the plane into nearest site cells bounded by perpendicular bisectors, turning proximity, nearest neighbor, and largest empty circle questions into simple cell lookups.