# Voronoi diagrams: basic construction

> IB Mathematics Applications and Interpretation HL · IB DP AI HL
> Source: https://www.owlsprep.com/study/ib-math-ai-hl-u3-voronoi-diagrams-basic-construction/

This sub-topic introduces the core structure of Voronoi diagrams, teaches manual construction using perpendicular bisectors, and explains how to identify nearest-neighbor regions. We focus on exam-relevant constructions with up to 4 sites.

**Prerequisites:** [Perpendicular bisectors of line segments](https://www.owlsprep.com/study/ib-math-ai-hl-u3-perpendicular-bisectors/); [Distance formula in 2D coordinate geometry](https://www.owlsprep.com/study/ib-math-ai-hl-u1-distance-formula-coordinate-geometry/)

## Learning objectives

- Recall the definition and key properties of Voronoi diagrams
- Construct a Voronoi diagram manually for up to 4 sites
- Identify nearest neighbor regions and boundary points
- Find the equation of Voronoi edges using perpendicular bisectors

## Key Definitions and Core Properties

**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:
1. Every edge is a segment of the perpendicular bisector between two adjacent sites
2. Every vertex is the intersection of three perpendicular bisectors, and is equidistant to three sites
3. All points inside a cell are strictly closer to the cell's site than any other site

> **info**
>
> IB AI HL exams only require manual construction for 2 to 4 sites. Problems with more sites always use digital methods, covered in a separate sub-topic.

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

## Manual Construction for 2 and 3 Sites

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=mx+c$ or $ax+by+c=0$). Double-check your perpendicular gradient calculation, this is the most commonly marked error.

## Manual Construction for 4 Sites

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 $AB$ (left pair) is $(3,1)$, $AB$ is horizontal, so perpendicular bisector is vertical line $x=3$. Midpoint of $AC$ (top-bottom) is $(1,3)$, $AC$ 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$.

**Check your understanding**

Test your understanding:

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

   *Why:* Correct. A Voronoi vertex is always equidistant to three sites. Sites are the original input points, and cells are the regions.

## Common pitfalls

- **Wrong:** Using the negative of the original gradient instead of the negative reciprocal for the perpendicular bisector.
  - Why it fails: Many students mix up perpendicular gradient rules, leading to incorrect edge equations.
  - Correct: If original gradient is $m$, perpendicular gradient is $-\frac{1}{m}$. A horizontal line has a vertical perpendicular bisector, and vice versa.
- **Wrong:** Using the entire infinite perpendicular bisector as an edge, even for 3+ sites.
  - Why it fails: Only the segment of the bisector that forms a boundary between regions is part of the Voronoi diagram.
  - Correct: After finding vertices, discard all parts of perpendicular bisectors that lie inside a Voronoi cell.
- **Wrong:** Using visual estimation to assign points to cells instead of calculation.
  - Why it fails: Points near edges often look closer to the wrong site, and exam markers require proof.
  - Correct: Always calculate squared distance from the point to every site to confirm which cell it belongs to.
- **Wrong:** Drawing perpendicular bisectors between non-adjacent sites unnecessarily.
  - Why it fails: This creates extra unrelated lines that lead to confusion and incorrect vertex identification.
  - Correct: Only draw bisectors between sites that are clearly closest to each other first, then find intersections.

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

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

- [Voronoi diagrams: application problems](https://www.owlsprep.com/study/ib-math-ai-hl-u3-voronoi-diagrams-application-problems/)
- [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-basic-construction/