Voronoi diagrams
In a minute
A splits a map into cells, one per , so each point belongs to its nearest site. You find edges as , add sites, estimate values from the nearest site, and find the point furthest from all sites.
You'll be able to
- Name the sites, , and of a Voronoi diagram, and find the site closest to a point.
- Find the equation of an edge from two sites, and the coordinates of a vertex.
- Add a site to a Voronoi diagram and find its new edges and vertices.
- Estimate values with , and find the area of a cell.
- Solve the by comparing the vertices.
Before you start3 quick questions on what this builds on
Revise first: 2.1 Straight-line equations, 2.6 Fitting and testing models and 3.5 Perpendicular bisectors
Sites, cells, edges and vertices
A town has three libraries, and each reader uses the nearest one. A Voronoi diagram shows which streets belong to which library.
The site closest to a point is the site of the cell it lies in. Near an edge, don't trust your eye: calculate the distances with (prior learning in the booklet).
Try it first, then reveal one step at a time.
- is near an edge, so calculate each distance.
- km.
- km.
- km.
- is the smallest, so lies in the cell of B.
- Library B: is closer to B ( km) than to A or C.
Try it first, then reveal one step at a time.
- is on the edge between A and B, so . It is also on the edge between B and C, so .
- km.
- Check: km and km.
- is a vertex, so it is equidistant from all three libraries: km from each.
Equations of edges and vertices
Exams give the sites' coordinates, and you calculate the equation of an edge: it lies on the perpendicular bisector of its two sites (3.5). You never construct it.
1. Find the midpoint of the two sites.
2. Find the gradient of the segment joining them.
3. have gradients that multiply to , so if the edge has gradient .
4. Put the midpoint and the edge's gradient into .
Both formulas are in the booklet. Sites with the same -coordinate have a vertical edge through their midpoint; sites with the same -coordinate, a horizontal one.
Try it first, then reveal one step at a time.
- Midpoint: .
- Gradient of BC: .
- The edge is perpendicular, so its gradient is .
- , so .
- Check: is on it, as .
A vertex lies on two edges, so solve their equations simultaneously. Your GDC can do this.
Try it first, then reveal one step at a time.
- (a) Midpoint of A and B: . Gradient of AB: , so the edge has gradient .
- , so .
- (b) Write down what you solve: and . The GDC's intersection is , .
- So the vertex is to 3 s.f.
- (c) It is equally far, about km, from all three stations.
Adding a site
A new site takes area from the cells around it. Cells far away don't change.
1. Find the cell the new site lies in.
2. Draw the bisector of the new site and that cell's site, until it meets an old edge: a new vertex.
3. Continue along the bisector with the site across that edge. Repeat until the new cell closes. If you reach the boundary of the region, go back and trace the first bisector the other way too.
4. Erase the old edges inside the new cell.
Try it first, then reveal one step at a time.
- F–H: midpoint , gradient of FH , so the edge is , or .
- G–H: midpoint , gradient of GH , so the edge is , or .
- The new vertex is on the old edge : , so . The old edge now stops there.
Try it first, then reveal one step at a time.
- (a) , and . is the smallest.
- (b) D and B are level, so their edge is vertical through the midpoint : . D and C are one above the other, so their edge is .
- (c) The two edges meet where and .
- (d) , less than , so is now inside the cell of D.
Nearest neighbour interpolation and cell areas
A rain gauge measures rainfall at one place. The simplest estimate anywhere else copies the nearest gauge.
It is a kind of : estimating between known data points. It is quick but rough: it ignores every site except the nearest.
Try it first, then reveal one step at a time.
- (a) km.
- km and km.
- P is nearest, so the farm is in the cell of P and gets P's reading.
- (b) The farm is only about km further from Q and R, which recorded quite different amounts ( mm and mm), so the estimate is rough.
- F is nearest to P, so the estimate is mm.
For the area of a cell, find its corners from the edges' equations. Then split it into rectangles, triangles and trapezoids.
Try it first, then reveal one step at a time.
- (a) Midpoint . Gradient of ST: , so the edge has gradient : , so .
- (b) The edge meets at and at . So the cell of S is a trapezoid with parallel sides and units, units apart.
- Area square units.
- square unit is , so the area is .
The toxic waste dump problem
A waste dump should be placed well away from people. Now the sites are towns, and you want the point whose distance to the nearest town is largest.
Why a vertex? Moving away from your nearest site helps until you reach an edge, then moving along the edge helps until you reach a vertex. In real regions the best point can be on the boundary. In IB exams it is always a vertex where three edges meet.
Try it first, then reveal one step at a time.
- The best point is a vertex, so compare and .
- is equidistant from P, Q and R: km.
- is equidistant from P, R and S: km.
- , so the dump goes at , km from the nearest villages.
Try it first, then reveal one step at a time.
- (a) Midpoint of C and D: . Gradient of CD: , so the edge has gradient .
- , so .
- (b) Solve and on the GDC, as in the ambulance example: the vertex is .
- (c) From to its site B: km.
- From to its site D: km.
- , so build at .
- (d) The model treats each village as a point and ignores roads and wind.
Common mistakes
- Using the segment's gradient for the edge. Use its negative reciprocal.
- Writing a point without brackets, or an edge as just a gradient. Give and a full equation.
- Judging the nearest site by eye near an edge. Calculate the distances.
- Scaling an area by the scale, not its square: unit km means square unit .
- Rounding a vertex before using it. Keep the GDC's full values.
- Averaging readings in nearest neighbour interpolation. Use the nearest site only.
Exam tips
- Justify the nearest site: say the point is in its cell, or closer to it than to any other site.
- Find an edge: show the midpoint, the gradient and the perpendicular gradient. Any correct form is fine unless one is asked for.
- Write down both equations before the GDC's vertex: that earns the method mark. Give coordinates in brackets, to 3 s.f.
- Interpret a vertex: equally far from its three sites, with no site closer.
Key takeaways
Practise this
12 past-paper questions on Voronoi diagrams in the AI HL bank, each with a mark scheme and a worked explanation.