Computational geometry

Voronoi Diagrams From First Principles

How one nearest-site rule turns distance tests into cells, edges, and local competitors.

First draft. Geometry before algorithms, lifting, and language-model analogies.

Put four clinics on a city map and impose one rule: every address is served by the clinic closest to it. The rule is local. It only talks about one address at a time. Applied everywhere, it forces the whole map to break into territories.

The Local Rule

Start with two clinics, p and q. The addresses tied between them are exactly the points x where the distance to p equals the distance to q.

||x - p|| = ||x - q||

Squaring both sides removes the square roots. After expansion, the x.x terms cancel. What remains is linear in x, so the tie set is a line: the perpendicular bisector of the segment from p to q. One side belongs to p; the other belongs to q.

Figure 1. Repeated Cutting A Voronoi cell is the territory that survives every pairwise contest against its competitors.
p q r s Each dashed line removes points where a competitor is closer.

Cells Are Intersections

Adding a third clinic does not change the rule. It adds another contest. The region for p must lie on the p-side of the bisector between p and q, and also on the p-side of the bisector between p and r. Every new site contributes one more half-plane.

V(p_i) = {x : ||x - p_i|| <= ||x - p_j|| for every j != i}

That expression is the whole cell. A half-plane is convex, and an intersection of convex sets stays convex. A Voronoi cell can be unbounded, but it cannot have a dent. The boundary may run forever for a site on the outside of the point set; it still remains a convex polygonal chain.

Local Neighbors

Stand at a point where three cells meet. If the tied sites are p, q, and r, then the point is equally far from all three sites.

||x - p|| = ||x - q|| = ||x - r||

So there is a circle centered at x passing through p, q, and r. No other site can sit inside that circle. If one did, it would be closer to x than the three tied sites, and the three-way boundary point would disappear.

Connect two sites whenever their Voronoi cells share an edge. The resulting graph is the Delaunay graph. The Voronoi diagram organizes territory; the Delaunay graph records which sites are genuine local competitors.

Figure 2. Empty-Circle Certificate A three-way Voronoi vertex is the center of an empty circle through the three neighboring sites.
p q r Voronoi vertex

Sparse Structure

The definition talks about every pair of sites, but the final diagram keeps only local rivalries. In a generic planar input with n sites and h sites on the convex hull, the Delaunay triangulation has 3n - 3 - h edges and 2n - 2 - h triangles.

Duality transfers those counts back to the Voronoi diagram. Voronoi edges correspond to Delaunay edges, and Voronoi vertices correspond to Delaunay triangles. Since h >= 3, the planar Voronoi diagram has at most 3n - 6 edges and 2n - 5 vertices. The all-pairs rule collapses to a linear-size structure.