Voronoi Diagrams

Given a finite set S = {p₁, p₂, …, pₙ} of sites in the plane, the Voronoi cell V(pᵢ) of site pᵢ is the set of all points x such that d(x, pᵢ) ≤ d(x, pⱼ) for every j ≠ i, where d denotes Euclidean distance. Algebraically, each cell is the intersection of n−1 half-planes, one for each other site, so every Voronoi cell is a convex polygon (possibly unbounded if the site is on the convex hull of S).

The boundary shared between V(pᵢ) and V(pⱼ) lies exactly on the perpendicular bisector of segment pᵢpⱼ. This bisector passes through the midpoint M = ((xᵢ+xⱼ)/2, (yᵢ+yⱼ)/2) and is perpendicular to the direction vector (xⱼ−xᵢ, yⱼ−yᵢ). Not every perpendicular bisector becomes a full edge; it is clipped by the half-planes from all other sites, so an edge exists only where two cells are actually adjacent.

A Voronoi vertex is a point equidistant from exactly three (or more, in degenerate cases) sites. It is the circumcentre of the triangle formed by those three sites — the centre of the circle passing through all three. If this circumscribed circle contains no other site in its interior, the vertex is a genuine Voronoi vertex. This connection links Voronoi diagrams directly to Delaunay triangulation, their geometric dual.

Nearest-neighbour interpolation assigns to any query point q the value of whichever site's cell contains q. Because each cell contains exactly the points closest to its site, finding the nearest site is equivalent to locating the cell containing q. This is used in meteorology (assigning the nearest weather-station reading to every map location), image scaling, and geographic information systems. It is the simplest interpolation method: fast but discontinuous at cell boundaries.

Suppose n sites represent populated centres and you must place a toxic waste dump as far as possible from all of them. The point that maximises the minimum distance to any site is called the largest empty circle centre. It always occurs at a Voronoi vertex (or on the boundary of the region of interest). So the algorithm is: (1) construct the Voronoi diagram, (2) evaluate the minimum distance to any site at each Voronoi vertex, (3) choose the vertex with the largest such minimum distance. This converts a continuous optimisation problem into a finite search over O(n) candidates.

When a new site pₙ₊₁ is inserted, only the cells that contained points now closer to pₙ₊₁ are affected. Concretely, the new cell V(pₙ₊₁) is carved out of existing cells; its boundary consists of arcs of perpendicular bisectors between pₙ₊₁ and each of its Voronoi neighbours. Cells not adjacent to pₙ₊₁ remain unchanged. This locality property means that incremental Voronoi construction, updating one site at a time, is practical for dynamic datasets.

• V(p_i) — Voronoi cell (—): The region of the plane assigned to site p_i; a convex polygon.
• x — query point (—): An arbitrary point in the plane being tested for membership in the cell.
• d(x, p_i) — Euclidean distance (length units): Straight-line distance from point x to site p_i, equal to sqrt((x₁−pᵢ₁)²+(x₂−pᵢ₂)²).
• p_j — competing site (—): Any site other than p_i; the inequality must hold for all such sites simultaneously.

Problem. Three towns are located at A = (0, 0), B = (6, 0), and C = (3, 4). A toxic waste dump must be placed as far as possible from all three towns. Find the optimal location and the maximum guaranteed distance.

Answer. Optimal dump location: (3, 7/8); maximum minimum distance = 25/8 = 3.125 units.

• Delaunay Triangulation — The Delaunay triangulation is the geometric dual of the Voronoi diagram: connect every pair of sites whose Voronoi cells share an edge, and you obtain a triangulation that maximises the minimum interior angle.
• Convex Hull — Sites on the convex hull of S have unbounded Voronoi cells; recognising the convex hull helps identify which cells extend to infinity.
• Perpendicular Bisectors — Every Voronoi edge lies on a perpendicular bisector between two sites, so mastering perpendicular bisector equations is essential for constructing Voronoi diagrams by hand.
• Circumscribed Circle (Circumcircle) — Voronoi vertices are circumcentres of triangles formed by three nearby sites, directly linking this topic to circumcircle constructions.
• Nearest-Neighbour Interpolation — Nearest-neighbour interpolation is the most direct application of Voronoi cells: the interpolated value at any point equals the value at the nearest site, found by identifying which cell contains the query point.