Voronoi Diagram — Definition, Formula & Examples

A Voronoi diagram is a partition of a plane into regions, where each region contains all the points closer to one specific site than to any other site. The boundaries between regions are segments of perpendicular bisectors of the line segments connecting neighboring sites.

Given a set of $n$ distinct points $S = \{p_1, p_2, \ldots, p_n\}$ in $\mathbb{R}^2$ (called sites or generators), the Voronoi cell of $p_i$ is the set $V(p_i) = \{x \in \mathbb{R}^2 \mid d(x, p_i) \leq d(x, p_j) \text{ for all } j \neq i\}$ , where $d$ denotes the Euclidean distance. The collection of all such cells and their boundaries forms the Voronoi diagram of $S$ .

Key Formula

V(p_i) = \{ x \in \mathbb{R}^2 \mid \|x - p_i\| \leq \|x - p_j\| \text{ for all } j \neq i \}

Where:

$p_i$ = The site (generator point) whose Voronoi cell is being defined
$x$ = An arbitrary point in the plane
$\|x - p_i\|$ = Euclidean distance from x to site p_i

How It Works

To construct a Voronoi diagram, start with a finite set of sites in the plane. For each pair of neighboring sites, compute the perpendicular bisector of the segment joining them. Each site's Voronoi cell is the intersection of all half-planes that contain that site, one half-plane per neighboring bisector. The result is a set of convex polygonal regions (some unbounded) that tile the entire plane with no gaps or overlaps. Efficient algorithms like Fortune's sweep-line algorithm compute Voronoi diagrams in

O(n \log n)

time.

Worked Example

Problem: Three sites are located at

A = (0, 0)

B = (6, 0)

, and

C = (3, 6)

. Find the point equidistant from all three sites (the Voronoi vertex).

Step 1: Find the perpendicular bisector of segment AB. The midpoint is

(3, 0)

and AB is horizontal, so the bisector is the vertical line

x = 3

x = 3

Step 2: Find the perpendicular bisector of segment AC. The midpoint is

(1.5, 3)

and the slope of AC is

6/3 = 2

, so the bisector has slope

-1/2

and equation

y - 3 = -\tfrac{1}{2}(x - 1.5)

, which simplifies to

y = -\tfrac{1}{2}x + 3.75

y = -\tfrac{1}{2}x + 3.75

Step 3: Substitute

x = 3

into the second bisector equation to find the intersection point.

y = -\tfrac{1}{2}(3) + 3.75 = 2.25

Answer: The Voronoi vertex, equidistant from all three sites, is at

(3, 2.25)

. This is where the three Voronoi cell boundaries meet.

Why It Matters

Voronoi diagrams appear in computational geometry, GIS applications (finding the nearest hospital or fire station), mesh generation for finite-element analysis, and crystallography. They are dual to Delaunay triangulations, making them central to many algorithms in discrete and computational geometry courses.

Common Mistakes

Mistake: Assuming all Voronoi cells are bounded polygons.

Correction: Cells on the convex hull of the site set extend to infinity. Only interior cells are bounded convex polygons.