17.13 Voronoi Diagrams Overview

Problem

Given a set of points, partition the plane into regions so that every location belongs to the region of its nearest point.

The input points are usually called sites.

A Voronoi diagram answers questions like:

Which hospital is closest to this address?
Which cell tower should serve this device?
Which warehouse is nearest to this customer?
Which sample point owns this part of the plane?

Voronoi diagrams appear in geographic information systems, robotics, wireless networks, computer graphics, mesh generation, nearest-neighbor search, biology, facility planning, and spatial analysis.

Solution

For each site, define its Voronoi cell as the set of points closer to that site than to any other site.

Given a site p, its cell is:

all points x such that
distance(x, p) <= distance(x, q)
for every other site q

The boundary between two sites is the perpendicular bisector of the segment joining them.

For two points:

p = (0, 0)
q = (4, 0)

the boundary is:

x = 2

Every point to the left of that line is closer to p. Every point to the right is closer to q.

With many sites, each Voronoi cell is the intersection of several half-planes.

Basic Geometry

Consider three sites:

      A

B             C

Each pair of sites defines a perpendicular bisector.

The bisectors meet at a point that is equally distant from all three sites. This point becomes a Voronoi vertex.

The diagram consists of:

cells
edges
vertices

A cell belongs to one site.

An edge separates two sites.

A vertex is equidistant from three or more sites.

Voronoi Cells as Half-Plane Intersections

For one site p, compare it with every other site q.

The set of points closer to p than q is a half-plane.

Therefore:

Voronoi cell of p =
intersection of half-planes induced by all other sites

This gives a simple conceptual algorithm:

for each site p:
    start with a large bounding box
    for each other site q:
        clip p's cell by the perpendicular bisector of p and q

This is easy to understand and useful for small inputs.

Naive complexity is high:

O(n²)

half-plane constraints, plus clipping work.

For production-scale construction, specialized algorithms are used.

Perpendicular Bisector

Given two sites:

p = (px, py)
q = (qx, qy)

The perpendicular bisector passes through the midpoint:

m = ((px + qx) / 2, (py + qy) / 2)

and has direction perpendicular to:

q - p

If:

q - p = (dx, dy)

a perpendicular direction is:

(-dy, dx)

The bisector divides the plane into two half-planes.

To keep the side closer to p, test which side contains p.

Simple Cell Construction Sketch

This sketch clips a large convex polygon against bisectors.

def voronoi_cell(site, sites, bounding_box):
    cell = bounding_box

    for other in sites:
        if other == site:
            continue

        halfplane = closer_halfplane(site, other)
        cell = clip_convex_polygon(cell, halfplane)

        if not cell:
            break

    return cell

The details depend on polygon clipping, which appears later in this chapter’s broader clipping patterns. The main point is structural: each cell can be built by repeated convex clipping.

Delaunay Duality

Voronoi diagrams are closely related to Delaunay triangulations.

Two sites share a Delaunay edge exactly when their Voronoi cells share a Voronoi edge.

Conceptually:

Voronoi diagram: regions of nearest influence
Delaunay triangulation: connect neighboring sites

This dual relationship is one of the most important facts in computational geometry.

It explains why Voronoi diagrams are useful for nearest-neighbor queries and why Delaunay triangulations are useful for mesh generation.

Algorithms for Construction

Several algorithms can build Voronoi diagrams.

Incremental Construction

Insert sites one at a time and update the diagram.

This is conceptually simple but can require careful handling of degeneracies.

Divide and Conquer

Split the sites, build diagrams recursively, and merge them.

This mirrors other geometric divide-and-conquer algorithms.

Fortune’s Algorithm

Fortune’s algorithm is the classic sweep-line algorithm for planar Voronoi diagrams.

It runs in:

O(n log n)

time and uses:

O(n)

space.

The algorithm sweeps a line across the plane while maintaining a structure called the beach line. It is powerful but more complex than the other algorithms introduced so far.

Nearest-Neighbor Queries

Once a Voronoi diagram is built, nearest-neighbor queries become geometric location queries.

Given a query point:

x

find the Voronoi cell containing x.

The site that owns that cell is the nearest site.

This reduces nearest-neighbor search to point location.

In practice, many systems use spatial indexes such as KD-trees or R-trees instead of explicitly building a full Voronoi diagram. Voronoi diagrams are most useful when the full spatial partition itself is needed.

Applications

Facility Planning

Given possible store, hospital, or warehouse locations, Voronoi cells show service regions.

Wireless Networks

Cell towers naturally induce approximate Voronoi regions.

Robotics

Voronoi edges often maximize clearance from obstacles and can guide safe paths.

Mesh Generation

Voronoi diagrams and Delaunay triangulations are fundamental tools for generating well-shaped meshes.

Computer Graphics

Procedural textures often use Voronoi noise to generate cellular patterns.

Biology and Ecology

Voronoi diagrams model territory, cell structures, and spatial competition.

Degenerate Cases

Voronoi construction must handle several special cases.

Duplicate sites produce undefined or zero-area cells.

Collinear sites can create unbounded cells and vertices at infinity.

Four or more sites on the same circle produce Voronoi vertices where more than three cells meet.

Very close sites can create narrow cells that are numerically unstable.

Many implementations avoid exact degeneracies by perturbing input slightly or by using robust geometric predicates.

Bounded vs Unbounded Cells

Sites on the convex hull of the input set have unbounded Voronoi cells.

For example, the leftmost site owns a region extending indefinitely to the left.

In practical applications, diagrams are often clipped to a bounding rectangle:

map extent
screen region
simulation domain

This turns all cells into bounded polygons and makes storage and rendering simpler.

Correctness Argument

A Voronoi cell for site p contains exactly the points satisfying all pairwise nearest-site inequalities:

distance(x, p) <= distance(x, q)

for every other site q.

Each inequality defines a half-plane bounded by the perpendicular bisector of p and q.

Intersecting all these half-planes therefore produces exactly the points closer to p than to any other site.

The full diagram is obtained by constructing one such region for every site.

Complexity Analysis

Naive cell construction compares every site against every other site.

For n sites:

O(n²)

pairwise bisectors are considered.

With polygon clipping included, the total cost may be higher depending on implementation.

Specialized algorithms such as Fortune’s algorithm construct the full diagram in:

O(n log n)

time.

Space usage for a planar Voronoi diagram is:

O(n)

under standard assumptions, because the number of cells, edges, and vertices is linear in the number of sites.

Common Pitfalls

Forgetting Unbounded Cells

Sites on the convex hull usually have cells extending to infinity. Clip to a bounding box when a finite representation is required.

Mishandling Duplicate Sites

Duplicate points should be removed or handled explicitly.

Assuming Every Vertex Has Degree Three

Four or more cocircular sites can produce higher-degree Voronoi vertices.

Building a Full Diagram for One Query

If the only task is nearest-neighbor lookup, a KD-tree or spatial hash may be simpler.

Ignoring Numeric Precision

Bisectors and intersections can be unstable for nearly coincident sites.

Discussion

Voronoi diagrams convert nearest-site relationships into geometry. Instead of repeatedly searching all sites, the plane is partitioned into ownership regions. This makes spatial influence visible and algorithmically useful.

The simplest way to understand a Voronoi cell is as a half-plane intersection. That connects the diagram directly to the previous section and provides a practical construction method for small inputs. For large inputs, sweep-line and divide-and-conquer algorithms are preferred, but the half-plane view remains the clearest mental model.