Voronoi diagrams: basic construction

IB Mathematics Applications and Interpretation HL· Unit 3: Geometry and trigonometry· 6 min read

1. Key Definitions and Core Properties★★☆☆☆⏱ 15 min

📘 Definition

Voronoi Diagram

A partition of a 2D plane into regions based on distance to a set of discrete input points called sites. Each region contains all points closer to its own site than any other site on the plane.

Example:

A map of hospitals where each region shows all locations for which that hospital is the closest emergency facility

All Voronoi diagrams follow three non-negotiable rules for IB exams:

Every edge is a segment of the perpendicular bisector between two adjacent sites
Every vertex is the intersection of three perpendicular bisectors, and is equidistant to three sites
All points inside a cell are strictly closer to the cell's site than any other site

📐 Worked Example

Three sites are at $A (1, 1)$ , $B (5, 1)$ and $C (3, 5)$ . Verify that the point $(2, 2)$ lies in the Voronoi cell for $A$ .

1
To confirm which cell a point belongs to, calculate the squared distance to each site (this avoids square roots and simplifies calculation):
2
Squared distance to A:
3
$(2-1)^2 + (2-1)^2 = 1 + 1 = 2$
4
Squared distance to B:
5
$(2-5)^2 + (2-1)^2 = 9 + 1 = 10$
6
Squared distance to C:
7
$(2-3)^2 + (2-5)^2 = 1 + 9 = 10$
8
Since $d_{A}^{2} < d_{B}^{2}$ and $d_{A}^{2} < d_{C}^{2}$ , $(2, 2)$ is closer to $A$ than any other site, so it belongs to $A$ 's Voronoi cell.

2. Manual Construction for 2 and 3 Sites★★☆☆☆⏱ 20 min

For two sites, construction is simple: the only Voronoi edge is the full infinite perpendicular bisector of the segment connecting the two sites, which splits the plane into two infinite regions. For three non-collinear sites, you construct three perpendicular bisectors (one for each pair of sites), which intersect at a single Voronoi vertex. The edges are the segments of the perpendicular bisectors running from the vertex out to infinity.

📐 Worked Example

Construct the Voronoi diagram for two sites at $P (0, 2)$ and $Q (4, 0)$ . Find the equation of the Voronoi edge.

1
Step 1: Calculate the midpoint of segment PQ:
2
$M = \left(\frac{0+4}{2}, \frac{2+0}{2}\right) = (2, 1)$
3
Step 2: Calculate the gradient of PQ, then the gradient of the perpendicular bisector:
4
$m_{PQ} = \frac{0-2}{4-0} = -\frac{1}{2} \implies m_{\perp} = 2$
5
Step 3: Use point-gradient form to find the equation of the line:
6
$y - 1 = 2(x - 2) \implies y = 2x - 3$
7
Step 4: Conclusion: This entire line is the Voronoi edge, splitting the plane into two regions (one for P, one for Q).

Exam tip:

Always write your edge equation in the form requested by the question (usually $y = m x + c$ or $a x + b y + c = 0$ ). Double-check your perpendicular gradient calculation, this is the most commonly marked error.

3. Manual Construction for 4 Sites★★★☆☆HL only⏱ 25 min

For four sites, the construction process follows the same core rule: every edge is a segment of a perpendicular bisector between adjacent sites. You first draw perpendicular bisectors between each pair of neighboring sites, find their intersections to get Voronoi vertices, then keep only the segments that form boundaries between regions.

📐 Worked Example

Four sites are at $A (1, 1)$ , $B (5, 1)$ , $C (1, 5)$ , $D (5, 5)$ . Construct the Voronoi diagram and find all edge equations.

1
Step 1: Find perpendicular bisectors between left/right and top/bottom pairs of sites:
2
Midpoint of $A B$ (left pair) is $(3, 1)$ , $A B$ is horizontal, so perpendicular bisector is vertical line $x = 3$ . Midpoint of $A C$ (top-bottom) is $(1, 3)$ , $A C$ is vertical, so perpendicular bisector is horizontal line $y = 3$ .
3
Step 2: Confirm bisectors for the remaining pairs: All other pairs have perpendicular bisectors that are also $x = 3$ or $y = 3$ .
4
Step 3: Find the Voronoi vertex: $x = 3$ and $y = 3$ intersect at $(3, 3)$ , which is equidistant to all four sites.
5
Step 4: Final edges: The Voronoi edges are the half-lines $x = 3$ for $y > 3$ and $y < 3$ , and $y = 3$ for $x < 3$ and $x > 3$ , splitting the plane into four regions (one per site). All edge equations are $x = 3$ and $y = 3$ .

✓ Quick check

Test your understanding:

What is the intersection of three perpendicular bisectors in a 3-site Voronoi diagram called?
- A. Voronoi site
- B. Voronoi cell
- C. Voronoi vertex
- D. Perpendicular intersection
Reveal answer
C —
Correct. A Voronoi vertex is always equidistant to three sites. Sites are the original input points, and cells are the regions.

4. Common Pitfalls

Wrong move:

Using the negative of the original gradient instead of the negative reciprocal for the perpendicular bisector.

Why:

Many students mix up perpendicular gradient rules, leading to incorrect edge equations.

Correct move:

If original gradient is $m$ , perpendicular gradient is $- \frac{1}{m}$ . A horizontal line has a vertical perpendicular bisector, and vice versa.

Wrong move:

Using the entire infinite perpendicular bisector as an edge, even for 3+ sites.

Why:

Only the segment of the bisector that forms a boundary between regions is part of the Voronoi diagram.

Correct move:

After finding vertices, discard all parts of perpendicular bisectors that lie inside a Voronoi cell.

Wrong move:

Using visual estimation to assign points to cells instead of calculation.

Why:

Points near edges often look closer to the wrong site, and exam markers require proof.

Correct move:

Always calculate squared distance from the point to every site to confirm which cell it belongs to.

Wrong move:

Drawing perpendicular bisectors between non-adjacent sites unnecessarily.

Why:

This creates extra unrelated lines that lead to confusion and incorrect vertex identification.

Correct move:

Only draw bisectors between sites that are clearly closest to each other first, then find intersections.

5. Quick Reference Cheatsheet

Component	Definition	Key Property
Site	Input point for the diagram	All points in its cell are closer to it than any other site
Voronoi Cell	Region assigned to one site	Boundaries are all perpendicular bisector segments
Voronoi Edge	Boundary between two cells	Segment of perpendicular bisector between two sites
Voronoi Vertex	Intersection of 3 edges	Equidistant to three adjacent sites
2-site diagram	Two infinite regions	Full perpendicular bisector is the only edge
3-site diagram	Three infinite regions	One Voronoi vertex, three edges

When this came up on past exams

AI-estimated based on syllabus patterns — cross-check with official past papers for accuracy. Use only as revision-focus signals.

2021 · 1
Short 3-site construction question
2023 · 2
6-mark 4-site construction problem

What's Next

Basic construction is the foundation for all applied Voronoi problems in IB AI HL. Voronoi diagrams are used to solve real-world problems from locating new facilities to mapping nearest services in geography and business. Next, you will learn how to solve the largest empty circle problem, which uses Voronoi vertices to find the optimal location for a new facility that is as far as possible from existing sites. You will also study how to add new sites to an existing Voronoi diagram, a common extended response question in exams.