Voronoi diagrams: application problems

IB Mathematics: Applications and Interpretation HL· Unit 3: Geometry and trigonometry, Voronoi diagrams· 15 min read

1. Optimal Placement of a New Facility★★★☆☆⏱ 5 min

A core application of Voronoi diagrams is finding the optimal location for a new facility that maximizes the minimum distance to existing competing facilities. This maximizes the new facility's potential customer base and reduces overlap with existing services.

📐 Worked Example

Three competing grocery stores are located at $(1, 2)$ , $(5, 2)$ and $(3, 6)$ on a 10×10 km city grid. A new grocery store is to be built to maximize the minimum distance to all three existing stores. Find the optimal coordinates.

1
First, find the perpendicular bisectors between each pair of existing sites:
2
$\text{Midpoint of } (1,2) \text{ and } (5,2) = (3,2), \text{ bisector: } x = 3 \\ \text{Midpoint of } (1,2) \text{ and } (3,6) = (2,4), \text{ bisector: } x + 2y = 10$
3
The optimal location is the Voronoi vertex, the intersection of the two bisectors. Substitute $x = 3$ into the second equation:
4
$3 + 2y = 10 \implies y = 3.5$
5
The optimal location is $(3, 3.5)$ , which is 2.5 km from all three existing sites.

2. The Largest Empty Circle Problem★★★★☆⏱ 6 min

The largest empty circle problem asks for the largest circle that can fit within a bounded Voronoi diagram that contains no existing sites in its interior. This is used to locate facilities that need to be as far as possible from existing populated areas, such as waste treatment plants.

📘 Definition

Largest Empty Circle

The maximum-size circle that fits within the boundary of the diagram with no sites inside it, with center at an internal Voronoi vertex or on the diagram boundary.

Example:

Used to find the safest location for a hazardous facility far from all residential areas.

📐 Worked Example

Four towns are located at sites $A (0, 0)$ , $B (4, 0)$ , $C (4, 4)$ , $D (0, 4)$ within a 4×4 km square boundary. Find the center and radius of the largest empty circle inside the boundary.

1
The perpendicular bisectors between opposite pairs of sites intersect at the only internal Voronoi vertex $(2, 2)$ .
2
Calculate the distance from $(2, 2)$ to the nearest site:
3
$d = \sqrt{(2-0)^2 + (2-0)^2} = \sqrt{8} = 2\sqrt{2} \approx 2.83$
4
Compare this to the maximum possible radius for circles on the boundary: all boundary positions produce a smaller maximum radius than $22$ .

3. Catchment Area Allocation★★☆☆☆⏱ 4 min

Voronoi diagrams divide an area into catchment regions where each region (Voronoi cell) contains all points closest to a single service site, such as a school, hospital, or store. Exams commonly ask you to estimate the area of a cell and calculate the population served by the site.

📐 Worked Example

A Voronoi cell for a new clinic is drawn on a grid where $1 cm = 2 km$ . The cell covers 12 full grid squares and 8 half squares. If the population density is 150 people per km², estimate the population served by the clinic.

1
Calculate the total estimated area of the cell in grid squares:
2
$12 + (8 \times 0.5) = 16 \text{ cm}^2$
3
Convert to actual area using the scale factor. For area, square the linear scale factor:
4
$1 \text{ cm} = 2 \text{ km} \implies 1 \text{ cm}^2 = 4 \text{ km}^2 \\ 16 \times 4 = 64 \text{ km}^2$
5
Calculate total population: $64 \times 150 = 9600$ people.

4. Common Pitfalls

Wrong move:

Placing the new facility at the average (mean) of the existing site coordinates

Why:

The average coordinate is not the point that maximizes the minimum distance to all sites

Correct move:

Find the Voronoi vertex at the intersection of perpendicular bisectors to get the optimal position

Wrong move:

Forgetting to check boundary edges when finding the largest empty circle

Why:

For bounded diagrams, the maximum circle can sometimes lie on the outer boundary, not at an internal vertex

Correct move:

Compare the maximum radius from internal vertices to the maximum possible radius on the boundary

Wrong move:

Not squaring the linear scale factor when converting grid area

Why:

Area is a two-dimensional measurement, so the scale factor must be squared

Correct move:

If $1 unit = k km$ , then $1 unit^{2} = k^{2} km^{2}$

Wrong move:

Relying on visual inspection to assign a point to a Voronoi cell

Why:

Visual distance can be misleading, especially for points close to an edge

Correct move:

Calculate the distance from the point to each site to confirm which is closest

5. Quick Reference Cheatsheet

Application	Key Location	Calculation Required
Optimal new facility	Voronoi vertex	Coordinates of bisector intersection
Largest empty circle	Internal vertex / boundary edge	Radius = distance to nearest site
Catchment area	Voronoi cell	Estimate area with grid counting
Closest service	Any point	Calculate distance to all sites

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 · 2
Optimal hospital placement problem
2022 · 2
Retail store location problem
2023 · 1
Largest empty circle calculation

Going deeper

syllabusOfficial IB AI HL SyllabusFull syllabus reference for this topic

What's Next

Voronoi diagram application problems are a common 6-8 mark question in IB AI HL Paper 2, often combining coordinate geometry, scale conversion, and problem solving. This topic connects geometric construction to real-world decision making used in urban planning, logistics, and geography. Building on your knowledge, you can explore more advanced spatial problems and optimization techniques.