# Voronoi diagrams: application problems

> IB Mathematics: Applications and Interpretation HL · Geometry and trigonometry
> Source: https://www.owlsprep.com/study/ib-math-ai-hl-u3-voronoi-diagrams-application-problems/

This subtopic covers common real-world applications of Voronoi diagrams, including optimal placement of new facilities, finding the largest empty circle, and allocating regions for planning and logistics.

**Prerequisites:** [Voronoi diagram construction](https://www.owlsprep.com/study/ib-math-ai-hl-u3-voronoi-diagrams-construction/); Perpendicular bisectors and coordinate geometry

## Learning objectives

- Solve optimal facility placement problems on Voronoi diagrams
- Find the largest empty circle for a given set of sites
- Estimate area of Voronoi cells for allocation problems
- Apply Voronoi diagrams to real-world decision making problems

## Optimal Placement of a New Facility

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.

> **tip**
>
> The optimal position for a new facility to maximize minimum distance will always be at a Voronoi vertex, never inside a Voronoi cell.

## The Largest Empty Circle Problem

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.

**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 $2\sqrt{2}$.

> **Exam tip**
>
> Always check boundary positions as well as internal vertices: the largest circle can sometimes lie on the outer edge of the diagram.

## Catchment Area Allocation

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 \text{ cm} = 2 \text{ 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.

> **warning**
>
> Always remember to square the linear scale factor when converting area units, this is a very common exam error.

## Common pitfalls

- **Wrong:** Placing the new facility at the average (mean) of the existing site coordinates
  - Why it fails: The average coordinate is not the point that maximizes the minimum distance to all sites
  - Correct: Find the Voronoi vertex at the intersection of perpendicular bisectors to get the optimal position
- **Wrong:** Forgetting to check boundary edges when finding the largest empty circle
  - Why it fails: For bounded diagrams, the maximum circle can sometimes lie on the outer boundary, not at an internal vertex
  - Correct: Compare the maximum radius from internal vertices to the maximum possible radius on the boundary
- **Wrong:** Not squaring the linear scale factor when converting grid area
  - Why it fails: Area is a two-dimensional measurement, so the scale factor must be squared
  - Correct: If $1 \text{ unit} = k \text{ km}$, then $1 \text{ unit}^2 = k^2 \text{ km}^2$
- **Wrong:** Relying on visual inspection to assign a point to a Voronoi cell
  - Why it fails: Visual distance can be misleading, especially for points close to an edge
  - Correct: Calculate the distance from the point to each site to confirm which is closest

## 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 |

## 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.

- [Calculus](https://www.owlsprep.com/study/ib-math-ai-hl-u4-overview/)

---

From [OwlsPrep](https://www.owlsprep.com) — free study guides for A-Level, IB, AP and IGCSE, written against the official syllabus. Canonical page: https://www.owlsprep.com/study/ib-math-ai-hl-u3-voronoi-diagrams-application-problems/