Voronoi Diagrams and Nearest-Site Geometry

Voronoi Diagrams and Nearest-Site Geometry

Part 15 used randomized incremental construction to locate a point inside a planar subdivision. Now suppose the subdivision itself should answer a geometric question: which stored site is closest to this query point? The Voronoi diagram turns that continuous optimization problem into point location. It partitions the plane into regions whose labels are nearest sites, making proximity visible as planar structure.

For a finite set of point sites \(S\subset\mathbb{R}^2\), the nearest-site Voronoi cell of \(p\in S\) is

\[ V(p)=\{x:\|x-p\|\leq \|x-q\|\text{ for every }q\in S\}. \]

The weak inequality deliberately assigns boundary points to more than one cell. Cell interiors have a unique nearest site; an edge represents a tie between two sites; and a vertex normally represents a tie among three. Once these cells have been built, nearest-neighbor search becomes: locate the query in the subdivision, then return its cell's label.

Bisectors carve out cells

For two point sites \(p\) and \(q\), the points equally distant from them form the perpendicular bisector of segment \(pq\). Squaring the distances cancels the quadratic terms:

\[ \|x-p\|^2\leq\|x-q\|^2 \quad\Longleftrightarrow\quad 2x\cdot(q-p)\leq \|q\|^2-\|p\|^2. \]

Thus the points at least as close to \(p\) as to \(q\) form a half-plane. Intersecting that half-plane over every competitor \(q\) produces \(V(p)\). Every point-site cell is therefore convex, although it may be unbounded or empty only if sites are weighted (ordinary distinct point sites always have nonempty cells).

Empty circles explain vertices

At a nondegenerate Voronoi vertex \(v\), three sites \(a,b,c\) are equally distant. They lie on a circle centered at \(v\). No other site may lie inside that circle: if one did, it would be closer to \(v\), contradicting the definition of the three incident cells. Conversely, the center of a circle through three sites whose interior contains no site becomes a Voronoi vertex.

This empty-circle property is the bridge to the Delaunay triangulation in Part 17. Connect two sites exactly when their Voronoi cells share an edge. Usually, three such connections surround each Voronoi vertex and form a Delaunay triangle. Voronoi and Delaunay are planar duals: cells correspond to sites, edges cross dual edges, and finite vertices correspond to triangles.

Why the diagram stays linear

A diagram of \(n\) distinct point sites may look elaborate, yet it has only linear complexity. Interpreted as a planar graph, it has exactly \(n\) faces, one per site. Under general position—no four sites cocircular and no three collinear—each finite Voronoi vertex has degree three. Euler's formula and degree counting then imply at most \(2n-5\) vertices and \(3n-6\) edges for \(n\geq3\); unbounded rays are accounted for by adding a vertex at infinity or enclosing the diagram in a large box.

The sites with unbounded cells are exactly the vertices of the sites' convex hull. Intuitively, an extreme site wins forever in some outward direction. An interior site is eventually beaten in every faraway direction. Consequently, the farthest-point and nearest-point diagrams expose complementary hull information.

Construct without comparing everything

A direct method intersects \(n-1\) half-planes for every site and is far too expensive for large inputs. Standard constructions achieve \(O(n\log n)\) time and \(O(n)\) space.

Divide and conquer sorts sites, recursively builds diagrams for left and right halves, then traces the bisector chain separating regions owned by the two halves. The merge resembles combining convex hulls, but maintaining a robust DCEL and clipping obsolete edges requires care.

Fortune's sweep moves a horizontal line across the plane. Processed sites influence a curved beach line made of parabolic arcs: each arc contains points equidistant from a processed site and the moving sweep line. A site event inserts an arc. A circle event removes an arc when three consecutive sites become cocircular; the disappearing breakpoint creates a Voronoi vertex. A balanced search tree maintains beach-line order and a priority queue schedules events, giving \(O(n\log n)\) time.

Circle events can become invalid when a later insertion changes the neighboring arcs. Implementations therefore attach event handles to arcs and lazily discard stale queue entries. Robust orientation and in-circle predicates are more important than attempting to compare rounded circumcenters.

fortune(sites):
    Q = site events ordered by sweep coordinate
    beach = empty balanced tree
    while Q is not empty:
        event = Q.pop()
        if event is stale: continue
        if event is a site:
            split the arc above the site
            create two moving breakpoints
        else:                       # valid circle event
            finish a Voronoi vertex
            remove the vanishing arc
        invalidate changed circle events
        schedule new events for new neighboring triples
    extend unfinished breakpoint rays to infinity

from math import hypot

def nearest_site(query, sites):
    """Baseline oracle for testing a Voronoi point-location result."""
    qx, qy = query
    return min(sites,
               key=lambda p: ((p[0]-qx)**2 + (p[1]-qy)**2, p))

def on_bisector(x, p, q, eps=1e-9):
    dp = hypot(x[0]-p[0], x[1]-p[1])
    dq = hypot(x[0]-q[0], x[1]-q[1])
    return abs(dp-dq) <= eps * max(1.0, dp, dq)

# Use nearest_site as an independent checker: sample queries in each
# constructed face and confirm that the face label matches the oracle.

The scan is intentionally not a construction algorithm—it costs \(O(n)\) per query—but it is an excellent test oracle. After preprocessing a Voronoi subdivision for point location, queries take \(O(\log n)\) time with linear storage; with a walk from a nearby previous query, coherent workloads are often faster in practice.

Beyond point sites

The same nearest-owner definition supports richer sites, but the geometry changes.

For line-segment sites, distance means the minimum distance to any point on the segment. A segment's region is influenced by its interior and endpoints; pairwise bisectors can contain line and parabolic pieces rather than one straight line. Shared endpoints and intersecting or overlapping segments require declared ownership rules. The diagram still supports proximity to roads, strokes, and polygon boundaries, but generic point-site code cannot simply be reused.

The farthest-point Voronoi diagram assigns each query to its farthest site. Only convex-hull sites have nonempty cells: an interior point can never be uniquely farthest. Its cells are generally unbounded, and its dual is a triangulation of the convex hull. A farthest-site query is useful for smallest-enclosing-circle reasoning and worst-case facility distance.

For a polygonal boundary treated as a collection of segments, points having two or more closest boundary features trace the medial axis. Imagine expanding a disk centered at an interior point until it touches the boundary; centers where the maximal disk touches in at least two places lie on the axis. The medial axis is a skeleton of shape, useful for clearance paths and thickness, although tiny boundary perturbations can create long spurious branches.

Degeneracies are part of the model

Production code needs policies before construction begins:

• Duplicate sites: deduplicate them or store multiple labels on one site. Otherwise zero-length bisectors and contradictory event identities appear.
• Collinear sites: there may be no finite Voronoi vertices; consecutive sites are separated by parallel bisector lines. Algorithms must not assume every edge has two endpoints.
• Cocircular sites: four or more cells can meet at one vertex. Preserve the higher-degree vertex or apply a consistent symbolic perturbation; arbitrary floating-point tie breaking can damage topology.
• Unbounded features: represent rays explicitly by origin and direction, or clip only for display. A viewport boundary is not a Voronoi edge.
• Near ties: use exact or filtered predicates for orientation and in-circle decisions. A distance epsilon may help user-facing classification, but it cannot reliably decide combinatorial structure at every scale.

These cases also clarify the conceptual payoff. A Voronoi diagram is not merely a picture made from bisectors; it is a certified record of which competitor wins everywhere, including ties and infinity. Part 15 supplied the machinery for navigating subdivisions. Here that machinery became a nearest-site query engine. Part 17 turns the diagram over and studies its Delaunay dual, where empty circles become edges and triangles with strong geometric properties.