# Voronoi diagrams and closest site problems

> IB Mathematics AI SL · IB Math AI SL: Unit 3 Geometry & Trigonometry
> Source: https://www.owlsprep.com/study/ib-math-ai-sl-u3-voronoi-diagrams-and-closest-site/

This module covers how Voronoi diagrams partition space based on proximity to sites, how to solve closest site problems, and common IB exam applications including partial diagram construction and the largest empty circle problem.

**Prerequisites:** [Coordinate geometry: midpoint and distance formula](https://www.owlsprep.com/study/ib-math-ai-sl-u2-coordinate-geometry-basics/); [Equations of straight lines](https://www.owlsprep.com/study/ib-math-ai-sl-u1-equations-of-lines/)

## Learning objectives

- Identify key components of a Voronoi diagram
- Construct perpendicular bisectors for Voronoi edges
- Solve closest site problems for any given point
- Apply Voronoi diagrams to solve the largest empty circle problem

## 1. Key Definitions and Core Properties

**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. Solving Closest Site Problems

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.

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

> **tip**
>
> If the point lies exactly on a Voronoi edge, it is equidistant to both adjacent sites — the exam will accept either answer in this case.

## 3. Constructing Voronoi Edges

To find the Voronoi edge between two sites, you calculate the perpendicular bisector of the segment connecting the sites, following these steps:
1. Find the midpoint of the two sites
2. Calculate the gradient of the segment connecting the sites
3. Find the negative reciprocal gradient for the perpendicular bisector
4. 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 = mx + 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$$

**Check your understanding**

Test your understanding:

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

   - (2, 4)
   - (4, 2)
   - (2, 2)
   - (4, 4)

   *Answer:* (2, 4)

   *Why:* Correct! Midpoint is the average of the x-coordinates and the average of the y-coordinates.

## 4. The Largest Empty Circle Problem

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.

**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)$.

> **info**
>
> In exams, you will usually be given all candidate Voronoi vertices, so you only need to calculate the distance for each and select the maximum.

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

## Common pitfalls

- **Wrong:** Using the gradient of the original segment between sites instead of the negative reciprocal
  - Why it fails: This gives a parallel line, not a perpendicular bisector, so the Voronoi edge is wrong
  - Correct: Remember that perpendicular gradients multiply to -1, so always take the negative reciprocal
- **Wrong:** Forgetting to check boundary points for the largest empty circle in a bounded region
  - Why it fails: If the boundary is far from all sites, the maximum circle will be centred on the boundary, not at an internal vertex
  - Correct: Always check all candidate points, including boundary points of the given region
- **Wrong:** Claiming a Voronoi vertex is equidistant from only two sites
  - Why it fails: Vertices are intersections of three edges, so they are equidistant from three sites, not two
  - Correct: Remember: edges are equidistant to two sites, vertices are equidistant to three sites
- **Wrong:** Miscalculating squared distance when comparing closest sites
  - Why it fails: Comparing squared distance saves time, but arithmetic errors lead to wrong results
  - Correct: Double-check your calculations, or use actual distance (square root) to confirm

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

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

- [Triangle area formula for non-right triangles](https://www.owlsprep.com/study/ib-math-ai-sl-u3-triangle-area-formula-for-non/)
- [Statistics and Probability](https://www.owlsprep.com/study/ib-math-ai-sl-u4-overview/)
- [Discrete and continuous data types](https://www.owlsprep.com/study/ib-math-ai-sl-u4-discrete-and-continuous-data-types/)

---

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-sl-u3-voronoi-diagrams-and-closest-site/