This note covers Voronoi diagrams: how a plane is divided into regions by the nearest site, how to find the edges and vertices using perpendicular bisectors, and how to use the diagram to estimate values and to choose locations. Voronoi diagrams are used to plan emergency services, mobile networks, weather maps and shop locations.
Key ideas
A Voronoi diagram starts with a set of points called sites, such as hospitals, mobile masts or weather stations. It divides the plane into cells. Every point inside the cell of a site is closer to that site than to any other site.
Edges. The boundary between two neighbouring cells is an edge. Every point on an edge is the same distance from the two sites on either side. So an edge lies on the perpendicular bisector of the line segment joining those two sites. An edge may be a line segment or a half-line that extends without end.
Vertices. A vertex is a point where three (or more) edges meet. It is the same distance from three (or more) sites. A vertex is the centre of a circle that passes through those sites and has no other site inside it.
Finding a perpendicular bisector. For sites \(P(x_1, y_1)\) and \(Q(x_2, y_2)\):
- Find the midpoint \(M = \left(\dfrac{x_1 + x_2}{2}, \dfrac{y_1 + y_2}{2}\right)\).
- Find the gradient of \(PQ\), \(m = \dfrac{y_2 - y_1}{x_2 - x_1}\). The gradient of the bisector is \(-\dfrac{1}{m}\).
- Write the line through \(M\) with that gradient: \(y - y_M = -\dfrac{1}{m}(x - x_M)\).
If \(PQ\) is horizontal, the bisector is vertical, \(x = x_M\). If \(PQ\) is vertical, the bisector is horizontal, \(y = y_M\).
Finding a vertex. Find two of the perpendicular bisectors of the three sites and solve them simultaneously, by hand or using the GDC. As a check, the distances from the vertex to the three sites should be equal. The third bisector must pass through the same point.
Adding a new site. When a site is added, the new cell takes in the part of the plane that is closer to the new site than to any old site. Draw the perpendicular bisectors between the new site and its neighbours. Some old edges are shortened or removed, and some new vertices appear. The cells of the old sites can only get smaller.
Nearest-neighbour interpolation. If each site has a measured value, such as a temperature or rainfall, then estimate the value at any other point by using the value of the site whose cell contains that point. To find which cell contains the point, compare its distances to the sites, or use the edges of the diagram.
Largest empty circle (the "toxic waste" problem). To place a facility as far as possible from all existing sites, such as a waste dump, look at the vertices of the diagram. The best position is at a vertex, and the distance from the vertex to its three sites gives the radius of the largest circle that has no site inside it. If the possible area has a boundary, such as a region on a map, also check where the edges meet the boundary and the corners of the boundary.
Other uses. Cells can be used to compare the size of the area each site serves. The area of a cell that is a polygon can be found using the coordinates of its vertices and standard geometry. Equations of the edges give the exact limits of each cell, for example "the cell of A is where \(x \lt 3\)".
Definitions and formulae
| Term or formula | Meaning / when to use |
|---|---|
| Site | A given point that defines a cell. |
| Cell | The region of points closer to one site than to any other. |
| Edge | A line segment or half-line on the perpendicular bisector between two sites. |
| Vertex | A point where edges meet, equidistant from three or more sites. |
| \(M = \left(\dfrac{x_1 + x_2}{2}, \dfrac{y_1 + y_2}{2}\right)\) | Midpoint of two sites. |
| \(m_{\perp} = -\dfrac{1}{m}\) | Gradient of the perpendicular bisector, where \(m\) is the gradient of the line joining the sites. |
| \(d = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\) | Distance between two points. |
| Nearest-neighbour interpolation | Estimate a value at a point as the value at the nearest site. |
Worked examples
Example 1 Three sites have coordinates \(A(0, 0)\), \(B(6, 0)\) and \(C(2, 6)\). Find the equations of the perpendicular bisectors of \(AB\) and \(AC\), and the coordinates of the vertex of the Voronoi diagram.
\(AB\) is horizontal, with midpoint \((3, 0)\). The perpendicular bisector is the vertical line \(x = 3\).
\(AC\): the midpoint is \((1, 3)\) and the gradient is \(\dfrac{6 - 0}{2 - 0} = 3\). The perpendicular gradient is \(-\dfrac{1}{3}\).
\(y - 3 = -\dfrac{1}{3}(x - 1)\), so \(y = -\dfrac{1}{3}x + \dfrac{10}{3}\).
The vertex is where these lines meet. At \(x = 3\): \(y = -1 + \dfrac{10}{3} = \dfrac{7}{3}\).
Check with distances: \(VA^2 = 3^2 + \left(\dfrac{7}{3}\right)^2 = 14.44\), \(VB^2 = (-3)^2 + \left(\dfrac{7}{3}\right)^2 = 14.44\), and \(VC^2 = 1^2 + \left(\dfrac{7}{3} - 6\right)^2 = 1 + 13.44 = 14.44\). All three are equal.
Answer: \(x = 3\) and \(y = -\dfrac{1}{3}x + \dfrac{10}{3}\); vertex \(\left(3, \dfrac{7}{3}\right)\).
Example 2 Three weather stations are at \(S_1(1, 2)\) with temperature 14 °C, \(S_2(7, 3)\) with 18 °C and \(S_3(4, 9)\) with 11 °C (coordinates in km). Use nearest-neighbour interpolation to estimate the temperature at the point \(P(5, 5)\).
Find the distance from \(P\) to each station.
\(PS_1 = \sqrt{(5-1)^2 + (5-2)^2} = \sqrt{25} = 5\) km.
\(PS_2 = \sqrt{(5-7)^2 + (5-3)^2} = \sqrt{8} = 2.83\) km.
\(PS_3 = \sqrt{(5-4)^2 + (5-9)^2} = \sqrt{17} = 4.12\) km.
The nearest station is \(S_2\), so \(P\) is in the cell of \(S_2\). The estimate is the value at \(S_2\).
Answer: 18 °C.
Example 3 Using the sites from Example 1, a new site \(D(6, 6)\) is added. (a) Find the perpendicular bisectors of \(CD\) and \(BD\). (b) Find the new vertex where these meet the bisector of \(BC\), and the radius of the empty circle there.
(a) \(C(2, 6)\) and \(D(6, 6)\) are on a horizontal line, with midpoint \((4, 6)\). The bisector is \(x = 4\).
\(B(6, 0)\) and \(D(6, 6)\) are on a vertical line, with midpoint \((6, 3)\). The bisector is \(y = 3\).
(b) These two bisectors meet at \((4, 3)\).
Check that this point is on the bisector of \(BC\). The midpoint of \(BC\) is \((4, 3)\), so it is on that bisector.
Distances: to \(D\), \(\sqrt{(6-4)^2 + (6-3)^2} = \sqrt{13}\). To \(B\), \(\sqrt{(6-4)^2 + 3^2} = \sqrt{13}\). To \(C\), \(\sqrt{(2-4)^2 + (6-3)^2} = \sqrt{13}\).
The new vertex is equidistant from \(B\), \(C\) and \(D\), and the radius of the empty circle is \(\sqrt{13} = 3.61\) (3 s.f.).
Answer: (a) \(x = 4\) and \(y = 3\); (b) vertex \((4, 3)\), radius 3.61.
Common errors
- Drawing an edge through the sites themselves instead of on the perpendicular bisector.
- Using the gradient of the line joining the sites as the gradient of the bisector, instead of its negative reciprocal.
- Finding a vertex from only one bisector. Two bisectors must be solved, and the third should be used as a check.
- Choosing the site with the greatest distance, or a point on an edge, when the nearest site is needed.
- Extending edges past the vertex, where a different pair of sites is nearer and the edge no longer applies.
Exam tip: Sketch the sites first and plan roughly where the edges should go. A sketch quickly shows if a calculated vertex or bisector is in the wrong place.
Check yourself
- Find the equation of the perpendicular bisector of \(P(1, 1)\) and \(Q(5, 7)\).
Answer
The midpoint is \((3, 4)\). The gradient of \(PQ\) is \(\dfrac{6}{4} = 1.5\), so the perpendicular gradient is \(-\dfrac{2}{3}\). The line is \(y - 4 = -\dfrac{2}{3}(x - 3)\), which is \(2x + 3y = 18\). - Sites are at \(A(0, 0)\) and \(B(8, 0)\) only. Which site's cell contains \((3, 10)\)?
Answer
The edge is the perpendicular bisector \(x = 4\). Since \(3 \lt 4\), the point is in the cell of \(A\). Check: distance to \(A\) is \(\sqrt{109}\) and to \(B\) is \(\sqrt{125}\). - A Voronoi vertex is at \((4, 3)\) and one of its three sites is \((6, 6)\). How far is the vertex from each of the other two sites?
Answer
A vertex is equidistant from its three sites. The distance to \((6, 6)\) is \(\sqrt{2^2 + 3^2} = \sqrt{13} = 3.61\), so the other two sites are also 3.61 away. - Rainfall is 40 mm at \(R(0, 0)\) and 55 mm at \(S(10, 0)\). Estimate the rainfall at \((7, 3)\) by nearest-neighbour interpolation.
Answer
The distance to \(R\) is \(\sqrt{49 + 9} = 7.62\) and to \(S\) is \(\sqrt{9 + 9} = 4.24\). The point is nearer to \(S\), so the estimate is 55 mm.