Voronoi diagrams and closest site problems

IB Mathematics AI SL· Unit 3: Geometry and Trigonometry, Topic 6· 15 min read

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

📘 Definition

Voronoi Diagram

A Voronoi diagram partitions a plane into regions (cells) based on distance to a set of points called sites. Every point in a cell is closer to the cell's site than any other site.

Example:

A map of hospitals where each region shows which hospital is closest to any address.

Every edge of a Voronoi diagram is a segment of the perpendicular bisector of the line connecting two sites. Voronoi vertices are the intersection points of three edges, and are equidistant from all three adjacent sites.

📐 Worked Example

Three sites are at A(1, 3), B(3, 5) and C(5, 3). Verify that the point (3, 3) is equidistant from all three sites.

1
Recall the distance formula between two points $(x_{1}, y_{1})$ and $(x_{2}, y_{2})$ :
2
$d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}$
3
Calculate distance from (3,3) to A(1,3):
4
$d_A = \sqrt{(3-1)^2 + (3-3)^2} = \sqrt{2^2 + 0^2} = 2$
5
Calculate distance from (3,3) to B(3,5):
6
$d_B = \sqrt{(3-3)^2 + (3-5)^2} = \sqrt{0^2 + (-2)^2} = 2$
7
Calculate distance from (3,3) to C(5,3):
8
$d_C = \sqrt{(3-5)^2 + (3-3)^2} = \sqrt{(-2)^2 + 0^2} = 2$
9
All distances are equal, so (3,3) is confirmed to be equidistant from all three sites.

Exam tip:

Voronoi vertices are always equidistant from three sites — this is a common exam check point.

2. 2. Solving Closest Site Problems★★☆☆☆⏱ 4 min

To find which site is closest to a given test point, you can either use an existing diagram to check which cell contains the point, or calculate the distance from the test point to each site and compare the values. Points on a Voronoi edge are equidistant to the two adjacent sites.

📘 Definition

Closest Site Problem

The problem of identifying which pre-existing site is the nearest to any given point in the plane. Common applications include finding the nearest emergency service or retail location.

📐 Worked Example

Two sites are at S₁(0, 0) and S₂(4, 0). Which site is closest to the point P(1, 2)?

1
Calculate distance from P to S₁:
2
$d_1 = \sqrt{(1-0)^2 + (2-0)^2} = \sqrt{1 + 4} = \sqrt{5} \approx 2.24$
3
Calculate distance from P to S₂:
4
$d_2 = \sqrt{(1-4)^2 + (2-0)^2} = \sqrt{9 + 4} = \sqrt{13} \approx 3.61$
5
Compare the distances: $d_{1} < d_{2}$ , so S₁ is the closest site.

3. 3. Constructing Voronoi Edges★★★☆☆⏱ 6 min

To find the Voronoi edge between two sites, you calculate the perpendicular bisector of the segment connecting the sites, following these steps:

Find the midpoint of the two sites
Calculate the gradient of the segment connecting the sites
Find the negative reciprocal gradient for the perpendicular bisector
Write the full equation of the bisector

📐 Worked Example

Find the equation of the perpendicular bisector (Voronoi edge) between sites A(2, 4) and B(6, 2).

1
Calculate the midpoint M of AB:
2
$M = \left(\frac{2+6}{2}, \frac{4+2}{2}\right) = (4, 3)$
3
Calculate the gradient of segment AB:
4
$m_{AB} = \frac{2 - 4}{6 - 2} = \frac{-2}{4} = -\frac{1}{2}$
5
Find the gradient of the perpendicular bisector (negative reciprocal):
6
$m_{\perp} = 2$
7
Substitute midpoint (4,3) into $y = m x + c$ to find the y-intercept:
8
$3 = 2(4) + c \implies c = -5$
9
Final equation of the Voronoi edge:
10
$y = 2x - 5$

✓ Quick check

Test your understanding:

What is the midpoint between (0, 2) and (4, 6)?
- (2, 4)
- (4, 2)
- (2, 2)
- (4, 4)

4. 4. The Largest Empty Circle Problem★★★☆☆⏱ 5 min

The largest empty circle problem is a common optimization application of Voronoi diagrams. It asks for the optimal location of a new site such that the new site is as far as possible from all existing sites. The centre of the largest empty circle is always a Voronoi vertex, since these are the points furthest from all existing sites.

📘 Definition

Largest Empty Circle Problem

An optimization problem that finds the location for a new site that maximizes the minimum distance to all existing sites.

📐 Worked Example

Three existing fire stations are at A(1, 3), B(3, 5), C(5, 3). The only Voronoi vertex is at (3, 3), which is 2 units from each station. Find the optimal location for a new fire station that must be as far as possible from all existing stations.

1
Recall that the optimal location for the new station is the Voronoi vertex, which is the point furthest from all existing sites.
2
The Voronoi vertex in this case is (3, 3), with a minimum distance of 2 units to the nearest existing station.
3
Conclusion: The optimal location is $(3, 3)$ .

Exam tip:

Always check if the problem gives a bounded region: the maximum circle may be centred on the boundary, not just at an internal vertex.

5. Common Pitfalls

Wrong move:

Using the gradient of the original segment between sites instead of the negative reciprocal

Why:

This gives a parallel line, not a perpendicular bisector, so the Voronoi edge is wrong

Correct move:

Remember that perpendicular gradients multiply to -1, so always take the negative reciprocal

Wrong move:

Forgetting to check boundary points for the largest empty circle in a bounded region

Why:

If the boundary is far from all sites, the maximum circle will be centred on the boundary, not at an internal vertex

Correct move:

Always check all candidate points, including boundary points of the given region

Wrong move:

Claiming a Voronoi vertex is equidistant from only two sites

Why:

Vertices are intersections of three edges, so they are equidistant from three sites, not two

Correct move:

Remember: edges are equidistant to two sites, vertices are equidistant to three sites

Wrong move:

Miscalculating squared distance when comparing closest sites

Why:

Comparing squared distance saves time, but arithmetic errors lead to wrong results

Correct move:

Double-check your calculations, or use actual distance (square root) to confirm

6. Quick Reference Cheatsheet

Concept	Key Fact
Voronoi Cell	All points closer to one site than any other
Voronoi Edge	Perpendicular bisector, equidistant to two sites
Voronoi Vertex	Intersection of 3 edges, equidistant to three sites
Closest Site Problem	Compare distances or identify cell containing the point
Perpendicular Bisector	Midpoint + negative reciprocal gradient
Largest Empty Circle	Centre at Voronoi vertex, maximum minimum distance

7. Frequently Asked

Do I need to construct a full Voronoi diagram from scratch?

No, IB AI SL exams usually give a partial diagram to complete, or ask you to solve problems on an existing full diagram.

What is the largest empty circle problem used for?

It finds the optimal location for a new facility (hospital, shop, fire station) that is as far as possible from existing facilities to maximize accessibility.

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.

2023 · 2
Largest empty circle optimization
2022 · 1
Identify closest site to point
2021 · 2
Complete partial Voronoi diagram

Going deeper

syllabusIB AI SL Official SyllabusSee page 46 for topic requirements

What's Next

Voronoi diagrams are a key applied geometry topic in IB AI SL, and are often tested in Paper 2 alongside other optimization and real-world problem solving questions. After mastering this sub-topic, you can move on to more advanced optimization problems such as linear programming, which require similar coordinate geometry and critical thinking skills. You can also review core prerequisite concepts like midpoint, distance, and perpendicular lines to reinforce your understanding, as these form the foundation of all Voronoi diagram problems. Solidifying these skills will help you tackle any exam question on this topic.