Voronoi Diagrams

Which fire station is closest to your house? Which weather station’s rainfall reading best describes your farm? A Voronoi diagram answers questions like these at a glance: it splits a map into regions, one around each important point, so that every location belongs to the point nearest to it. Voronoi diagrams are used in urban planning, ecology, meteorology and the study of how diseases spread, and they’re built entirely from perpendicular bisectors.

Key ideas

The vocabulary

Sites are the given points (towns, schools, weather stations).
Each site has a cell: the region of all points closer to that site than to any other site.
An edge is a boundary between two neighbouring cells. Every point on the edge between sites $A$ and $B$ is the same distance from $A$ as from $B$ .
A vertex is a point where three (or more) edges meet. It is the same distance from three sites.

A Voronoi diagram with four sites. The two vertices are

(6, 6)

and

(7, 5)

; the point

P(8, 3)

is in the cell of

C

Edges are pieces of perpendicular bisectors

All the points equally far from $A$ and $B$ form the perpendicular bisector of $AB$ . So the edge between two neighbouring cells is part of that bisector. To find its equation:

Find the midpoint of the two sites.
Find the gradient of the segment joining them, and take the negative reciprocal.
Write the equation of the line through the midpoint with that gradient.

An edge usually stops at a vertex, where a third site becomes just as close. A vertex is where two edges cross, so you find it by solving the two edge equations simultaneously. It’s equidistant from its three sites (it’s the circumcentre of their triangle), which gives a good check.

In IB exams, the coordinates of the sites are given, and you won’t have to construct perpendicular bisectors with a compass. Questions may ask for the equation of an edge, the site closest to a given point, or the area of a cell.

Adding a site

To add a new site to an existing diagram:

Find the cell the new site lands in. Draw the perpendicular bisector between the new site and that cell’s site, inside that cell, until it meets an edge.
At that edge you cross into a neighbouring cell. Draw the bisector between the new site and that cell’s site, and keep going.
Continue around until you’re back where you started (or reach the boundary of the region).
Erase the old edges that are now inside the new cell.

The new cell takes area from its neighbours; cells that aren’t next to it don’t change.

Nearest-neighbour interpolation

If each site has a measured value (rainfall, temperature, pollution level), you can estimate the value anywhere else by using the value of the nearest site. In other words, every point in a cell is given the same value as its site. This is called nearest-neighbour interpolation. It’s quick and simple, though it jumps suddenly at each edge.

The toxic waste dump problem

Suppose something unpleasant (a toxic waste dump, a noisy airport) must be built inside a region, as far as possible from the nearest site. Inside a cell, you can always get further from the site by moving away from it, so the best point is never in the middle of a cell. Along an edge, the distance to the two sites is smallest at their midpoint and grows as you move away, so the farthest point on an edge is at one of its ends. That’s why the best location is at a vertex of the Voronoi diagram. To solve it:

List the vertices inside the region.
For each vertex, find its distance to one of its three sites (all three are equal).
Choose the vertex with the largest distance.

In general the boundary of the region (for example, its corners) can also need checking, but in IB exams the solution is always at a vertex where three edges meet.

Worked examples

All the examples use the diagram above. The sites are towns, $A(2, 8)$ , $B(4, 2)$ , $C(10, 2)$ and $D(10, 8)$ , in a region from $(0, 0)$ to $(12, 10)$ , with units in kilometres.

Example 1: Nearest site and interpolation

The yearly rainfall measured at the four towns is $A$ : $620$ mm, $B$ : $540$ mm, $C$ : $480$ mm, $D$ : $700$ mm. Use nearest-neighbour interpolation to estimate the yearly rainfall at a farm at $P(8, 3)$ .

Solution. The diagram shows $P$ in the cell of $C$ . To confirm, compare the squared distances from $P$ :

Site	$A$	$B$	$C$	$D$
Squared distance to $P$	$6^2 + 5^2 = 61$	$4^2 + 1^2 = 17$	$2^2 + 1^2 = 5$	$2^2 + 5^2 = 29$

$C$ is nearest, so the estimated rainfall at the farm is $480$ mm.

Example 2: The equation of an edge and a vertex

(a) Find the equation of the edge between the cells of $A$ and $B$ .
(b) The edge between $A$ and $D$ lies on the line $x = 6$ . Find the vertex where these two edges meet, and check that it is equidistant from $A$ , $B$ and $D$ .

Solution. (a) The midpoint of $AB$ is $\left(\dfrac{2 + 4}{2}, \dfrac{8 + 2}{2}\right) = (3, 5)$ . The gradient of $AB$ is $\dfrac{2 - 8}{4 - 2} = -3$ , so the perpendicular gradient is $\dfrac{1}{3}$ :

y - 5 = \frac{1}{3}(x - 3) \quad\Rightarrow\quad y = \frac{1}{3}x + 4

(b) Substitute $x = 6$ : $y = \dfrac{1}{3}(6) + 4 = 6$ . The vertex is $(6, 6)$ .

Check the distances from $(6, 6)$ :

\text{to } A: \sqrt{4^2 + 2^2} = \sqrt{20} \qquad \text{to } B: \sqrt{2^2 + 4^2} = \sqrt{20} \qquad \text{to } D: \sqrt{4^2 + 2^2} = \sqrt{20}

All three are equal. ✓

Example 3: Where to put the dump

A toxic waste dump is to be built in the region, as far as possible from the nearest town. Find its location and its distance from the nearest town.

Solution. The vertices are $(6, 6)$ and $(7, 5)$ .

$(6, 6)$ is $\sqrt{20} \approx 4.47$ km from each of $A$ , $B$ and $D$ (Example 2).
$(7, 5)$ is on the edges between $B$ , $C$ and $D$ : its distance to $B$ is $\sqrt{3^2 + 3^2} = \sqrt{18} \approx 4.24$ km (and the same to $C$ and $D$ ).

The larger distance is at $(6, 6)$ . Among the vertices, the best site for the dump is $(6, 6)$ , which is $\sqrt{20} \approx 4.47$ km from the nearest towns ( $A$ , $B$ and $D$ ). (In this particular region, a few boundary points happen to be equally far from their nearest town: the corner $(0, 0)$ and the points where edges meet the border at $(0, 4)$ and $(6, 10)$ are also $\sqrt{20}$ km away. Exam questions are set up so that the answer is a single vertex.)

Example 4: Adding a site

A new town $E$ is founded at $(6, 4)$ . It lands in the cell of $B$ , and its new cell will border the cells of all four towns, so its edges lie on the perpendicular bisectors of $AE$ , $BE$ , $CE$ and $DE$ .

(a) Find the equations of these four bisectors.
(b) Find the vertices of the new cell of $E$ , and its area.

Solution. (a) Use midpoint and perpendicular gradient each time:

Pair	Midpoint	Gradient of segment	Bisector
$A(2, 8)$ , $E(6, 4)$	$(4, 6)$	$-1$	$y = x + 2$
$B(4, 2)$ , $E(6, 4)$	$(5, 3)$	$1$	$y = -x + 8$
$C(10, 2)$ , $E(6, 4)$	$(8, 3)$	$-\frac{1}{2}$	$y = 2x - 13$
$D(10, 8)$ , $E(6, 4)$	$(8, 6)$	$1$	$y = -x + 14$

(b) Neighbouring bisectors meet at the new vertices:

\begin{aligned} x + 2 = -x + 8 &\quad\Rightarrow\quad (3, 5) && \text{(sites } A, B, E\text{)} \\ -x + 8 = 2x - 13 &\quad\Rightarrow\quad (7, 1) && \text{(sites } B, C, E\text{)} \\ 2x - 13 = -x + 14 &\quad\Rightarrow\quad (9, 5) && \text{(sites } C, D, E\text{)} \\ -x + 14 = x + 2 &\quad\Rightarrow\quad (6, 8) && \text{(sites } A, D, E\text{)} \end{aligned}

Each new vertex lies on an old edge. For example, $(3, 5)$ is on $y = \frac{1}{3}x + 4$ . The old edges inside the new cell (including both old vertices) are erased.

After adding

E(6, 4)

, its cell (shaded) has vertices

(6, 8)

(3, 5)

(7, 1)

and

(9, 5)

. The dashed old edges are removed.

For the area, split the cell along the horizontal diagonal from $(3, 5)$ to $(9, 5)$ , which has length $6$ . The top triangle reaches up to $(6, 8)$ , a height of $3$ ; the bottom triangle reaches down to $(7, 1)$ , a height of $4$ :

\text{Area} = \frac{1}{2}(6)(3) + \frac{1}{2}(6)(4) = 9 + 12 = 21 \text{ km}^2

Common mistakes

Joining the sites instead of bisecting them. Edges are perpendicular to the segment between two sites, through its midpoint. The segment $AB$ itself is not part of the diagram.

Using the gradient of the segment for the edge. The edge’s gradient is the negative reciprocal. In Example 2, $AB$ has gradient $-3$ , so the edge has gradient $\dfrac{1}{3}$ , not $-3$ or $3$ .

Drawing bisectors between sites that aren’t neighbours. Only cells that share a boundary have an edge between them. In the diagram above, $A$ and $C$ have no common edge, so their bisector isn’t used.

Forgetting to erase old edges when adding a site. After adding $E$ in Example 4, the old vertices $(6, 6)$ and $(7, 5)$ are inside $E$ ‘s cell and are no longer vertices. Any answer that still uses them (for example, for a new dump location) is out of date.

Choosing the smallest distance in the toxic waste problem. You want the vertex farthest from its nearest sites. Compute the distance from each vertex to one of its three sites, then pick the largest.

Deciding the nearest site by eye. Points near an edge are easy to misjudge. Compare (squared) distances, as in Example 1, or substitute into the edge equation to see which side the point is on.

Practice

1. (Warm-up) Use the four-site diagram (sites $A(2, 8)$ , $B(4, 2)$ , $C(10, 2)$ , $D(10, 8)$ ).

(a) Which sites share an edge with $B$ ?
(b) Which site is nearest to $Q(2, 5)$ ? Show working.

Solution

(a) $A$ , $C$ and $D$ . (The cell of $B$ touches all three.)

(b) $Q$ is close to the edge between $A$ and $B$ , so compare squared distances: to $A$ : $0^2 + 3^2 = 9$ ; to $B$ : $2^2 + 3^2 = 13$ . $C$ and $D$ are much further ( $73$ each). The nearest site is $A$ .

Another way: on the edge $y = \frac{1}{3}x + 4$ , at $x = 2$ we have $y \approx 4.67$ . $Q$ is above the edge, on $A$ ‘s side.

2. (Warm-up) Find the equation of the perpendicular bisector of the sites $P(1, 3)$ and $Q(5, 1)$ .

Solution

Midpoint: $(3, 2)$ . Gradient of $PQ$ : $\dfrac{1 - 3}{5 - 1} = -\dfrac{1}{2}$ , so the perpendicular gradient is $2$ .

y - 2 = 2(x - 3) \quad\Rightarrow\quad y = 2x - 4

3. (Core) Three sites are $X(0, 0)$ , $Y(8, 0)$ and $Z(0, 6)$ .

(a) Find the equations of the perpendicular bisectors of $XY$ , $XZ$ and $YZ$ .
(b) Find the vertex of the Voronoi diagram, and show it is equidistant from all three sites.

Solution

(a) $XY$ is horizontal with midpoint $(4, 0)$ , so its bisector is $x = 4$ . $XZ$ is vertical with midpoint $(0, 3)$ , so its bisector is $y = 3$ . $YZ$ has midpoint $(4, 3)$ and gradient $\dfrac{6 - 0}{0 - 8} = -\dfrac{3}{4}$ , so the perpendicular gradient is $\dfrac{4}{3}$ :

y - 3 = \frac{4}{3}(x - 4) \quad\Rightarrow\quad y = \frac{4}{3}x - \frac{7}{3}

(b) $x = 4$ and $y = 3$ meet at $(4, 3)$ , which also satisfies the third equation: $\frac{4}{3}(4) - \frac{7}{3} = 3$ . ✓

Distances: to $X$ : $\sqrt{4^2 + 3^2} = 5$ ; to $Y$ : $\sqrt{4^2 + 3^2} = 5$ ; to $Z$ : $\sqrt{4^2 + 3^2} = 5$ .

4. (Core) The four towns in the worked examples have weather stations recording these temperatures one afternoon: $A$ : $14^\circ\text{C}$ , $B$ : $17^\circ\text{C}$ , $C$ : $19^\circ\text{C}$ , $D$ : $15^\circ\text{C}$ . Use nearest-neighbour interpolation to estimate the temperature at (a) $(5, 7)$ and (b) $(9, 6)$ .

Solution

(a) Squared distances from $(5, 7)$ : $A$ : $9 + 1 = 10$ , $B$ : $1 + 25 = 26$ , $C$ : $25 + 25 = 50$ , $D$ : $25 + 1 = 26$ . Nearest is $A$ , so the estimate is $14^\circ\text{C}$ .

(b) Squared distances from $(9, 6)$ : $A$ : $49 + 4 = 53$ , $B$ : $25 + 16 = 41$ , $C$ : $1 + 16 = 17$ , $D$ : $1 + 4 = 5$ . Nearest is $D$ , so the estimate is $15^\circ\text{C}$ .

5. (Core) In the four-site diagram (before $E$ is added), find the area of (a) the cell of $C$ and (b) the cell of $A$ .

Solution

(a) The cell of $C$ is bounded by $x = 7$ , $y = 5$ and the region’s edges $x = 12$ and $y = 0$ : a $5 \times 5$ square, with area $25 \text{ km}^2$ .

(b) The cell of $A$ has vertices $(0, 4)$ , $(6, 6)$ , $(6, 10)$ and $(0, 10)$ . It’s a trapezium with parallel vertical sides of length $10 - 4 = 6$ (on $x = 0$ ) and $10 - 6 = 4$ (on $x = 6$ ), a distance $6$ apart:

\text{Area} = \frac{6 + 4}{2} \times 6 = 30 \text{ km}^2

6. (Core) Four wells are at $P(1, 1)$ , $Q(7, 1)$ , $R(7, 9)$ and $S(11, 5)$ in a region from $(0, 0)$ to $(12, 10)$ (units in km). In the Voronoi diagram, the cell of $P$ borders the cells of $Q$ and $R$ , and the cell of $S$ borders the cells of $Q$ and $R$ .

(a) Find the equation of the edge between $P$ and $R$ .
(b) Find the equation of the edge between $Q$ and $S$ .
(c) The edge between $P$ and $Q$ is $x = 4$ and the edge between $Q$ and $R$ is $y = 5$ . Find the vertex where the cells of $P$ , $Q$ and $R$ meet.

Solution

(a) Midpoint of $PR$ : $(4, 5)$ . Gradient of $PR$ : $\dfrac{9 - 1}{7 - 1} = \dfrac{4}{3}$ , so the perpendicular gradient is $-\dfrac{3}{4}$ :

y - 5 = -\frac{3}{4}(x - 4) \quad\Rightarrow\quad y = -\frac{3}{4}x + 8

(b) Midpoint of $QS$ : $(9, 3)$ . Gradient of $QS$ : $\dfrac{5 - 1}{11 - 7} = 1$ , so the perpendicular gradient is $-1$ :

y - 3 = -(x - 9) \quad\Rightarrow\quad y = -x + 12

(c) $x = 4$ and $y = 5$ meet at $(4, 5)$ . Check it’s on the edge from (a): $-\frac{3}{4}(4) + 8 = 5$ . ✓ The vertex is $(4, 5)$ .

7. (Core) In the diagram from question 6, the only other vertex is $(7, 5)$ , where the cells of $Q$ , $R$ and $S$ meet. A waste incinerator is to be built at a vertex of the Voronoi diagram, as far as possible from the nearest well. Find its location and its distance from the nearest well.

Solution

$(4, 5)$ : distance to $P$ is $\sqrt{3^2 + 4^2} = 5$ km (the same to $Q$ and $R$ ).
$(7, 5)$ : distance to $Q$ is $\sqrt{0^2 + 4^2} = 4$ km (the same to $R$ and $S$ ).

The incinerator should be at $(4, 5)$ , $5$ km from the nearest wells.

8. (Challenge) A new well $T(9, 3)$ is added to the diagram from question 6.

(a) Find the equations of the perpendicular bisectors of $QT$ , $RT$ and $ST$ .
(b) Show that $(5, 5)$ and $(8, 6)$ are vertices of the new cell of $T$ , by showing that each is equidistant from three sites.
(c) Which vertex of the old diagram is removed? Justify your answer.

Solution

(a)

Pair	Midpoint	Gradient	Bisector
$Q(7, 1)$ , $T(9, 3)$	$(8, 2)$	$1$	$y = -x + 10$
$R(7, 9)$ , $T(9, 3)$	$(8, 6)$	$-3$	$y = \frac{1}{3}x + \frac{10}{3}$
$S(11, 5)$ , $T(9, 3)$	$(10, 4)$	$1$	$y = -x + 14$

(b) $(5, 5)$ lies on the first two bisectors: $-5 + 10 = 5$ and $\frac{5}{3} + \frac{10}{3} = 5$ . Its distances to $Q$ , $R$ and $T$ are $\sqrt{2^2 + 4^2}$ , $\sqrt{2^2 + 4^2}$ and $\sqrt{4^2 + 2^2}$ , all equal to $\sqrt{20}$ .

$(8, 6)$ lies on the last two bisectors: $\frac{8}{3} + \frac{10}{3} = 6$ and $-8 + 14 = 6$ . Its distances to $R$ , $S$ and $T$ are $\sqrt{1^2 + 3^2}$ , $\sqrt{3^2 + 1^2}$ and $\sqrt{1^2 + 3^2}$ , all equal to $\sqrt{10}$ .

(c) The old vertex $(7, 5)$ is removed. It was $4$ km from $Q$ , $R$ and $S$ , but it is only $\sqrt{2^2 + 2^2} = \sqrt{8} \approx 2.83$ km from $T$ . So it is now inside the cell of $T$ , not on a boundary.

9. (Challenge) Three villages are at $X(0, 0)$ , $Y(10, 0)$ and $Z(4, 8)$ (units in km). A clinic is to be built at the point equally far from all three villages. Find its coordinates and its distance from each village.

Solution

The point is the Voronoi vertex of the three sites, where the perpendicular bisectors meet.

Bisector of $XY$ : $x = 5$ .

Bisector of $XZ$ : midpoint $(2, 4)$ , gradient of $XZ$ is $2$ , so the perpendicular gradient is $-\dfrac{1}{2}$ :

y - 4 = -\frac{1}{2}(x - 2)

At $x = 5$ : $y = 4 - \dfrac{3}{2} = \dfrac{5}{2}$ . The clinic is at $(5,\ 2.5)$ .

Distances: to $X$ : $\sqrt{5^2 + 2.5^2} = \sqrt{31.25}$ ; to $Y$ : $\sqrt{5^2 + 2.5^2} = \sqrt{31.25}$ ; to $Z$ : $\sqrt{1^2 + 5.5^2} = \sqrt{31.25}$ . Each is $\sqrt{31.25} \approx 5.59$ km.