The Central Idea
Let
\[ S=\{P_1,P_2,\ldots,P_n\} \]be a finite set of sites in the plane.
The Voronoi cell of site \(P_i\) is the set of all points at least as close to \(P_i\) as to every other site:
\[ \boxed{ V(P_i)= \{X:\|X-P_i\|\le\|X-P_j\|\text{ for all }j\} }. \]The collection of all cells forms the Voronoi diagram.
A Nearest-Site Partition
Every ordinary location in the plane belongs to the region of its nearest site.
If one site is strictly closest, the location lies in the interior of that site's cell.
If two or more sites tie for closest, the location lies on a Voronoi boundary.
Two Sites
Begin with two sites
\[ A \qquad\text{and}\qquad B. \]The points equally distant from them satisfy
\[ \|X-A\|=\|X-B\|. \]This locus is the perpendicular bisector of segment \(AB\).
Deriving the Perpendicular Bisector Algebraically
Let
\[ A=(a_x,a_y), \qquad B=(b_x,b_y), \qquad X=(x,y). \]Equal squared distances give
\[ (x-a_x)^2+(y-a_y)^2 = (x-b_x)^2+(y-b_y)^2. \]Expanding causes the \(x^2\) and \(y^2\) terms to cancel.
The Bisector Becomes a Linear Equation
After expansion and simplification,
\[ 2(b_x-a_x)x+ 2(b_y-a_y)y = b_x^2+b_y^2-a_x^2-a_y^2. \]Thus the equal-distance boundary between two point sites is a line:
\[ \boxed{ \text{the perpendicular bisector of }AB }. \]Each Pair of Sites Defines a Half-Plane Test
For site \(P_i\) to own a point \(X\), we need
\[ \|X-P_i\|\le\|X-P_j\| \]for every competing site \(P_j\).
Each such inequality defines a half-plane bounded by the perpendicular bisector of \(P_iP_j\).
Therefore, an ordinary Voronoi cell is an intersection of half-planes.
Voronoi Cells Are Convex
Every half-plane is convex.
The intersection of convex sets is convex.
Therefore, every ordinary Euclidean point-site Voronoi cell is convex.
\[ \boxed{ V(P_i)\text{ is convex} }. \]Bounded and Unbounded Cells
Sites deep inside the point set often have bounded Voronoi cells.
Sites on the convex hull have cells that extend to infinity.
This is not accidental. A hull site has directions in which no other site lies farther outward to stop its region.
Convex Hull and Unbounded Voronoi Cells
In general position, a site has an unbounded Voronoi cell exactly when it lies on the convex hull of the site set.
Thus the outer structure of the point set appears in both:
- the convex hull;
- the unbounded part of the Voronoi diagram.
Voronoi Edges
A Voronoi edge consists of points equally close to two sites and no closer to any other site.
If cells \(V(A)\) and \(V(B)\) share an edge, then every point on that edge satisfies
\[ \|X-A\|=\|X-B\|. \]The edge lies on the perpendicular bisector of \(AB\).
Voronoi Vertices
A Voronoi vertex is typically a point where three Voronoi cells meet.
Such a point is equally distant from three sites:
\[ \boxed{ \|X-A\| = \|X-B\| = \|X-C\| }. \]Geometrically, \(X\) is the circumcenter of triangle \(ABC\).
Circumcenters Connect Voronoi and Triangulation
Three noncollinear sites determine a triangle and a unique circumcircle.
Its center is equidistant from all three sites.
If the corresponding circumcircle contains no other site in its interior, that center becomes a Voronoi vertex.
Delaunay Duality
The Voronoi diagram and Delaunay triangulation are geometric duals.
If two Voronoi cells share an edge, connect their generating sites.
Those site-to-site connections form the Delaunay graph.
\[ \boxed{ \text{Voronoi adjacency} \longleftrightarrow \text{Delaunay edge} }. \]Voronoi Vertices and Delaunay Triangles
A typical Voronoi vertex where three cells meet corresponds to a Delaunay triangle whose vertices are the three generating sites.
Conversely, the circumcenter of a Delaunay triangle is a Voronoi vertex.
Why the Duality Matters
Some geometric questions are easier in one structure than the other.
Voronoi diagrams make nearest-site regions explicit.
Delaunay triangulations make neighborhood connectivity explicit.
Together, they provide complementary views of the same spatial data.
Example: Three Noncollinear Sites
Let
\[ A=(0,0), \qquad B=(6,0), \qquad C=(3,4). \]The perpendicular bisector of \(AB\) is
\[ x=3. \]The common intersection of the relevant perpendicular bisectors is the circumcenter of triangle \(ABC\).
Finding the Circumcenter in the Example
Since the triangle is symmetric about \(x=3\), the circumcenter has the form
\[ O=(3,y). \]Set its squared distances to \(A\) and \(C\) equal:
\[ 3^2+y^2=(y-4)^2. \]Thus
\[ 9+y^2=y^2-8y+16, \]so
\[ y=\frac78. \]Therefore,
\[ \boxed{ O= \left(3,\frac78\right) }. \]A Voronoi Cell as a System of Inequalities
Suppose \(P_i\) competes with sites \(P_j\).
Its cell is
\[ V(P_i) = \bigcap_{j\ne i} \{X:\|X-P_i\|\le\|X-P_j\|\}. \]Each comparison contributes one linear half-plane inequality after squared distances are expanded.
The cell is the intersection of all those constraints.
Incremental Cell Construction
One conceptual method constructs a single Voronoi cell by starting with the entire plane or a large bounding region.
For each competing site:
- construct the perpendicular bisector;
- keep the half-plane closer to the chosen site;
- clip the current region against that half-plane.
Repeated clipping produces the final cell.
Clipping Connects Voronoi Diagrams to Polygon Algorithms
Constructing a bounded Voronoi cell by half-plane intersection is a polygon clipping problem.
This connects Voronoi diagrams with earlier computational tools:
- line intersection;
- point-in-region tests;
- convex polygons;
- half-plane predicates.
Brute-Force Nearest-Site Classification
If the goal is only to classify one query point \(X\), a full Voronoi diagram may be unnecessary.
Compute
\[ d_i^2=\|X-P_i\|^2 \]for every site and choose the smallest value.
This requires
\[ O(n) \]distance comparisons per query.
Why Build the Diagram at All?
If many nearest-site queries will be asked for the same site set, preprocessing can be valuable.
The Voronoi diagram organizes the plane so that each query reduces to locating which cell contains the point.
This separates expensive preprocessing from repeated query work.
Divide-and-Conquer Construction
Voronoi diagrams can be built using divide-and-conquer.
- split the sites into smaller groups;
- construct diagrams for the groups;
- merge the partial diagrams.
This mirrors a general algorithmic strategy used throughout computational geometry.
Fortune's Sweep-Line Algorithm
A famous Voronoi construction method is Fortune's algorithm.
It sweeps a line across the plane while maintaining a changing structure called the beach line.
Site events and circle events determine when the diagram changes combinatorially.
Fortune's Algorithm Complexity
With suitable data structures, Fortune's algorithm constructs a planar Voronoi diagram in
\[ \boxed{ O(n\log n) } \]time and uses linear space.
Its details are more advanced, but its complexity shows that full diagrams can be built efficiently.
Voronoi Diagram Size
For \(n\) point sites in general position in the plane, the total number of Voronoi vertices and edges is linear in \(n\).
Thus the diagram itself has
\[ \boxed{ O(n) } \]combinatorial complexity.
General Position
Many textbook descriptions assume the sites are in general position.
Common assumptions include:
- no duplicate sites;
- no four sites lying on the same circle.
These assumptions simplify the diagram by avoiding higher-order degeneracies.
Cocircular Degeneracy
If four or more sites lie on the same circle, the circle center is equally distant from all of them.
More than three Voronoi cells can therefore meet at one vertex.
The dual Delaunay triangulation may no longer be unique.
Duplicate Sites
If two sites have exactly the same coordinates, they have identical distance to every query point.
The ordinary nearest-site partition can no longer distinguish them geometrically.
Implementations generally remove duplicates or attach multiple records to one geometric site.
Collinear Sites
Collinear sites still have a valid Voronoi diagram.
Their cell boundaries are perpendicular to the common site line.
The Delaunay structure degenerates from a two-dimensional triangulation into a chain-like adjacency structure.
Voronoi Diagrams Depend on the Distance Metric
The ordinary Voronoi diagram uses Euclidean distance:
\[ d_2(P,Q) = \sqrt{ (x_P-x_Q)^2+ (y_P-y_Q)^2 }. \]Changing the metric changes the shape of the cells and boundaries.
Manhattan-Distance Voronoi Diagrams
Under the Manhattan metric,
\[ d_1(P,Q) = |x_P-x_Q|+ |y_P-y_Q|. \]Equal-distance boundaries are no longer ordinary Euclidean perpendicular bisectors.
The resulting cells reflect the diamond-shaped geometry of \(L^1\) distance.
Chebyshev-Distance Partitions
Under the Chebyshev metric,
\[ d_\infty(P,Q) = \max( |x_P-x_Q|, |y_P-y_Q| ). \]Distance balls become axis-aligned squares.
The corresponding nearest-site partition therefore has different boundary geometry from either Euclidean or Manhattan Voronoi diagrams.
Weighted Voronoi Diagrams
In some applications, sites are not equally attractive.
A site may have a weight representing:
- cost;
- capacity;
- priority;
- response time;
- influence;
- service quality.
Weighted Voronoi diagrams modify the distance comparison accordingly.
Additively Weighted Distance
One simple weighted model uses
\[ \boxed{ d_w(X,P_i)= \|X-P_i\|-w_i }. \]A larger positive weight effectively makes the site more competitive over a larger region.
Different weighting models produce different kinds of weighted Voronoi diagrams.
Power Diagrams
Another important weighted partition uses the power distance
\[ \boxed{ \pi_i(X)= \|X-P_i\|^2-w_i }. \]The resulting cells form a power diagram.
Because squared-distance terms cancel pairwise, power-cell boundaries remain linear.
Spatial Partitions More Broadly
A Voronoi diagram is one example of a spatial partition.
More generally, a spatial partition divides a domain into nonoverlapping regions according to some rule.
Rules may depend on:
- proximity;
- coordinates;
- hierarchy;
- visibility;
- ownership;
- cost or influence.
Grids as Spatial Partitions
A rectangular grid partitions the plane using fixed coordinate intervals.
Unlike a Voronoi diagram, grid cells are determined by the coordinate system rather than by site locations.
Grids are simple, regular, and useful for indexing, raster data, and numerical approximation.
Quadtrees
A quadtree recursively divides a two-dimensional region into four smaller quadrants.
Dense or geometrically complicated areas may be subdivided more deeply than sparse areas.
This produces an adaptive hierarchical partition.
Binary Space Partitions
A binary space partition repeatedly divides a region using lines or hyperplanes.
Each cut separates space into two subregions.
The resulting tree structure can support visibility, rendering, spatial search, and geometric organization.
Voronoi Diagrams for Facility Placement
Suppose sites represent hospitals, warehouses, stores, or service centers.
The Voronoi cell of each facility identifies locations for which that facility is geographically nearest under the chosen metric.
This provides a first-order service territory model.
Largest Empty Circle
One classic geometric problem asks for the largest circle that contains no sites in its interior while remaining within a permitted region.
Candidate centers often occur at:
- Voronoi vertices;
- intersections of Voronoi edges with the domain boundary;
- special boundary locations.
Voronoi structure therefore reduces the search space.
Nearest Neighbors
If two sites share a Voronoi edge, they are natural nearest-neighbor candidates.
The Delaunay dual records these adjacencies directly.
Many proximity algorithms therefore move freely between Voronoi and Delaunay representations.
Voronoi Diagrams in Natural Patterns
Voronoi-like partitions appear in models of:
- cellular tissue;
- crystal growth;
- territorial behavior;
- foam and grain structure;
- ecological competition.
These models should be interpreted according to their physical assumptions, but the same nearest-site geometry often provides a useful abstraction.
Voronoi Diagrams in Geographic Information Systems
GIS applications use Voronoi partitions to model proximity territories around:
- stations;
- schools;
- clinics;
- retail locations;
- sample points;
- infrastructure nodes.
Real travel networks may require network distance rather than Euclidean distance, but the partitioning principle remains similar.
Boundary Clipping
Ordinary Voronoi cells of hull sites extend infinitely.
Practical applications often restrict the diagram to a finite domain such as:
- a city boundary;
- a rectangular map window;
- a parcel boundary;
- a simulation domain.
The cells are then clipped to that domain.
Clipped Voronoi Area
Once cells are clipped to a bounded domain, their areas may be computed and compared.
If the cells partition the entire domain without gaps or overlap, then
\[ \boxed{ \sum_i \operatorname{Area}(V_i) = \operatorname{Area}(D) }. \]This provides a useful verification check.
Numerical Robustness
Voronoi construction depends on geometric decisions involving:
- equal distances;
- circumcenters;
- orientation;
- in-circle tests;
- line intersections.
Near-degenerate configurations can therefore create numerical difficulty.
Near-Equal Distances
Suppose two squared distances satisfy
\[ d_1^2 \approx d_2^2. \]A query point may lie very near a Voronoi boundary.
The application must decide whether approximate equality should be treated as a tie or resolved to one site.
Exact Predicates and Topology
A tiny sign error in an in-circle test can change Delaunay adjacency and therefore alter the dual Voronoi topology.
High-reliability implementations may use adaptive or exact geometric predicates to preserve combinatorial consistency.
Common Error: Assuming Voronoi Boundaries Are Arbitrary
In the ordinary Euclidean point-site case, every two-site boundary lies on a perpendicular bisector.
The shape of each cell follows directly from equal-distance geometry.
Common Error: Treating Every Cell as Bounded
Sites on the convex hull have unbounded cells unless the diagram is clipped to a finite domain.
A bounded plotting window should not be confused with the mathematical extent of the ordinary Voronoi diagram.
Common Error: Confusing a Voronoi Edge with a Delaunay Edge
A Voronoi edge is part of the nearest-site partition and lies between cells.
A Delaunay edge directly connects two sites whose Voronoi cells are adjacent.
These are dual objects, not the same geometric segment.
Common Error: Assuming the Diagram Is Unique under Every Degeneracy
The Voronoi partition itself remains well defined for ordinary point sites, but its dual Delaunay triangulation can become nonunique when several sites are cocircular.
Degenerate configurations require explicit structural conventions.
Common Error: Using Euclidean Voronoi Cells for Travel-Time Problems
Straight-line distance may not represent real accessibility.
Roads, terrain, barriers, and travel time can change which facility is effectively nearest.
The metric must match the application.
Common Error: Ignoring the Bounding Domain
A practical territory problem may exist only inside a specific region.
Computing an infinite Voronoi cell and using it without clipping can assign irrelevant area outside the actual domain.
A Reliable Procedure for Nearest-Site Classification
- Choose the distance metric appropriate to the problem.
- Compute the distance or squared distance from the query point to each site.
- Identify the minimum value.
- Detect ties according to the numerical policy.
- Return the nearest site or boundary classification.
A Reliable Procedure for Constructing One Euclidean Voronoi Cell
- Choose site \(P_i\).
- Start with the whole plane or a large bounding polygon.
- For each other site \(P_j\), construct the perpendicular bisector.
- Keep the half-plane closer to \(P_i\).
- Clip the current cell by that half-plane.
- Continue until every competitor has been processed.
- Return the remaining convex region.
A Reliable Procedure for a Practical Bounded Diagram
- Deduplicate the sites.
- Choose the distance model.
- Construct the Voronoi diagram with a suitable algorithm.
- Clip unbounded and partially bounded cells to the application domain.
- Resolve numerical ties consistently.
- Verify that clipped cells cover the domain without unintended gaps or overlaps.
- Build Delaunay adjacency as a dual structure when useful.
Practice 1: Equal-Distance Locus
What geometric object contains all points equally distant from two distinct point sites \(A\) and \(B\)?
Practice 2: Cell Membership
A point \(X\) satisfies
\[ \|X-A\|<\|X-B\| \]and
\[ \|X-A\|<\|X-C\|. \]Which of the three sites owns \(X\) in the ordinary Voronoi partition?
Practice 3: Voronoi Boundary
If
\[ \|X-A\|=\|X-B\| \]and both distances are smaller than the distance to every other site, where does \(X\) lie?
Practice 4: Convexity
Why is an ordinary Euclidean point-site Voronoi cell convex?
Practice 5: Hull Site
What kind of Voronoi cell does a site on the convex hull usually have in an unclipped planar diagram?
Practice 6: Voronoi-Delaunay Duality
What Delaunay feature corresponds to two Voronoi cells sharing an edge?
Practice 7: Voronoi Vertex
In general position, how many sites are usually equidistant from a Voronoi vertex?
Practice 8: Cocircular Sites
What special Voronoi behavior can occur when four sites lie on the same circle?
Practice 9: Metric Choice
Would a Manhattan-distance Voronoi diagram generally have the same cell boundaries as a Euclidean Voronoi diagram?
Practice 10: Domain Clipping
Why might a city-planning application clip a Voronoi diagram to the city boundary?
Practice Answers
Practice 1
The equal-distance locus is
\[ \boxed{ \text{the perpendicular bisector of }AB }. \]Practice 2
Site \(A\) is strictly closest, so
\[ \boxed{X\in V(A)}. \]Practice 3
The point lies on the shared Voronoi boundary between \(A\) and \(B\):
\[ \boxed{ X\text{ lies on a Voronoi edge} }. \]Practice 4
Each nearest-site comparison defines a half-plane, and the cell is the intersection of those half-planes. Intersections of convex sets are convex.
Practice 5
A hull site typically has
\[ \boxed{\text{an unbounded Voronoi cell}.} \]Practice 6
The two generating sites are connected by
\[ \boxed{\text{a Delaunay edge}.} \]Practice 7
In general position, a Voronoi vertex is usually equidistant from
\[ \boxed{3\text{ sites}.} \]Practice 8
All four cells can meet at the same Voronoi vertex, and the corresponding Delaunay triangulation may be nonunique.
Practice 9
No. Changing the distance metric changes equal-distance loci and therefore changes the cell geometry.
\[ \boxed{\text{No}.} \]Practice 10
The mathematical cells may extend beyond the geographic region of interest. Clipping restricts the service territories to the actual city domain.
What to Remember
Voronoi diagrams partition space by nearest-site relationships.
- a Voronoi cell contains points closest to one site;
- two-site boundaries lie on perpendicular bisectors;
- ordinary Euclidean Voronoi cells are convex;
- hull sites produce unbounded cells in the unclipped diagram;
- Voronoi edges represent two-site distance ties;
- Voronoi vertices are typically circumcenters of Delaunay triangles;
- Voronoi and Delaunay structures are geometric duals;
- different distance metrics produce different partitions;
- weighted models modify how sites compete for space;
- grids, quadtrees, and binary space partitions provide other ways to divide space;
- numerical robustness matters near equal-distance and cocircular configurations.
The larger computational principle is that a continuous space can be made easier to reason about by partitioning it into regions whose points share a common geometric relationship.
Where We Go Next
Voronoi diagrams partition space according to proximity. The next lesson turns from abstract spatial division to the practical construction of computational meshes.
Mesh Generation develops methods for turning geometric domains into collections of connected elements suitable for graphics, simulation, numerical analysis, and spatial modeling.