Voronoi Diagram

Partition the plane by “which site is nearest”. The Voronoi cell of a site $s$ is

$V(s)=\{p:|p-s|\le |p-t|\forall t\}.$

Each cell is a convex polygon (possibly unbounded) — the intersection of the half-planes defined by the perpendicular bisectors to every other site.

Structure

For $n$ sites in general position:

Quantity	Value
Cells	$n$
Edges	$\le 3n-6$
Vertices	$\le 2n-5$
Total complexity	$O(n)$

Voronoi vertices are circumcentres of triples of sites, and each is equidistant from three sites with no fourth inside that circle.

Construction

Method	Time	Note
Half-plane intersection per cell	$O(n^2\log n)$	simple, fine for $n\le 2000$
Fortune’s sweep	$O(n\log n)$	the classic; a parabolic beach line
Dual of Delaunay	$O(n\log n)$	build Delaunay, then take the dual
Lift to 3D + convex hull	$O(n\log n)$	elegant; via the paraboloid
Divide and conquer	$O(n\log n)$

Build Delaunay instead

The Voronoi diagram and the Delaunay triangulation are duals: a Voronoi edge separates two sites exactly when those sites are joined by a Delaunay edge. Delaunay is easier to construct (Bowyer-Watson is ~40 lines) and easier to store, so build it and dualise if you need the Voronoi structure explicitly.

The duality in detail

Voronoi	Delaunay
cell (a site)	vertex
edge (between 2 cells)	edge
vertex (meeting of 3 cells)	triangle
unbounded cell	a hull vertex
Voronoi vertex position	the triangle’s circumcentre

What it answers

Query	Via Voronoi/Delaunay
Nearest site to a query point	point location in the Voronoi diagram, $O(\log n)$
Closest pair	the shortest Delaunay edge
Euclidean MST	a subgraph of Delaunay — run Kruskal on $O(n)$ edges
Nearest neighbour graph	a subgraph of Delaunay
Largest empty circle	centred at a Voronoi vertex (or on the hull boundary)
Farthest-point Voronoi	gives the minimum enclosing circle
All nearest neighbours	one pass over Delaunay edges
Motion planning with maximum clearance	travel along Voronoi edges

The Euclidean MST reduction is the most valuable: it takes an $O(n^2)$ complete-graph problem down to $O(n\log n)$.

Variants

• Weighted (power) Voronoi — cells defined by $|p-s{|}^2-w_s$; still polygonal, dual to the regular triangulation.
• Multiplicatively weighted — cells bounded by Apollonius circles, no longer polygonal.
• Farthest-point Voronoi — “which site is farthest”; only hull vertices have non-empty cells.
• Order-$k$ Voronoi — regions with the same set of $k$ nearest sites.
• Voronoi under $L_1$ / $L_{\infty }$ — cells are still polygonal but with axis-parallel and diagonal edges.
• Voronoi of segments — cells bounded by parabolic arcs; substantially harder.

In competitive programming

Explicit Voronoi construction is rare — it is long, precision-sensitive, and usually avoidable. The three things worth knowing:

1. Nearest-site queries → a KD-tree is simpler and fast enough.
2. Euclidean MST → build Delaunay, then Kruskal.
3. Largest empty circle → its centre is a Voronoi vertex, a hull edge midpoint, or determined by the bounding region; enumerate the $O(n)$ candidates.

For small $n$, the $O(n^2\log n)$ per-cell half-plane intersection is entirely acceptable and far easier to get right.

See also: Delaunay Triangulation · Fortune’s Algorithm · Half-Plane Intersection