3.6 · SLPaper 1Paper 2

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
Check yourself
Find the midpoint of (3,8)(3, 8) and (9,2)(9, 2).
Check yourself
A line has gradient 25\frac{2}{5}. Write down the gradient of a line perpendicular to it.
Check yourself
Find the distance between (1,2)(1, 2) and (7,10)(7, 10).

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.

Voronoi diagram in a 12 by 10 rectangle with three sites, A at (2, 1), B at (11, 4) and C at (3, 8). Three dashed edges meet at the vertex V at (6, 4) and split the rectangle into three shaded cells, one around each site. 024681012246810 A (2, 1) B (11, 4) C (3, 8) V (6, 4) cell of Bcell of Acell of Cedge
Libraries A, B and C. The three edges meet at the vertex VV.

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 d=(x1−x2)2+(y1−y2)2d = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2} (prior learning in the booklet).

Worked exampleThe libraries in the figure are at A(2,1)A(2, 1), B(11,4)B(11, 4) and C(3,8)C(3, 8), with distances in km. A reader lives at H(7,2)H(7, 2). Find the library nearest to HH. Justify your answer.

Try it first, then reveal one step at a time.

  1. HH is near an edge, so calculate each distance.
Worked exampleThe town wants a book drop-off point that is equally far from all three libraries. Explain why the vertex V(6,4)V(6, 4) works, and find its distance from each library.

Try it first, then reveal one step at a time.

  1. VV is on the edge between A and B, so VA=VBVA = VB. It is also on the edge between B and C, so VB=VCVB = VC.
Check yourself
A point XX is inside the cell of site C, not on an edge. What must be true?
Check yourself
Library A is closed for repairs. A reader at (5,4)(5, 4) goes to the nearest open library. Which one?

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 mm of the segment joining them.

3. have gradients that multiply to −1-1, so if m≠0m \neq 0 the edge has gradient −1m-\frac{1}{m}.

4. Put the midpoint and the edge's gradient into y−y1=m(x−x1)y - y_1 = m(x - x_1).

In the formula booklet
m=y2−y1x2−x1m = \frac{y_{2} - y_{1}}{x_{2} - x_{1}}
In the formula booklet
y=mx+c;ax+by+d=0;y−y1=m(x−x1)y = mx + c; \quad ax + by + d = 0; \quad y - y_{1} = m(x - x_{1})

Both formulas are in the booklet. Sites with the same yy-coordinate have a vertical edge through their midpoint; sites with the same xx-coordinate, a horizontal one.

Worked exampleFind the equation of the edge between libraries B(11,4)B(11, 4) and C(3,8)C(3, 8). Give your answer in the form y=mx+cy = mx + c.

Try it first, then reveal one step at a time.

  1. Midpoint: (11+32,4+82)=(7,6)\left(\frac{11 + 3}{2}, \frac{4 + 8}{2}\right) = (7, 6).

A vertex lies on two edges, so solve their equations simultaneously. Your GDC can do this.

Worked exampleAmbulance stations are at A(7,2)A(7, 2), B(3,6)B(3, 6) and C(11,4)C(11, 4), with distances in km. (a) Find the equation of the boundary of the cells of A and B. (b) The boundary of the cells of B and C is y=4x−23y = 4x - 23. Use your calculator to find the vertex where the cells of A, B and C meet. Give your answer to 3 s.f. (c) Interpret the vertex in context.

Try it first, then reveal one step at a time.

  1. (a) Midpoint of A and B: (7+32,2+62)=(5,4)\left(\frac{7 + 3}{2}, \frac{2 + 6}{2}\right) = (5, 4). Gradient of AB: 6−23−7=−1\frac{6 - 2}{3 - 7} = -1, so the edge has gradient 11.
Check yourself
Two water fountains in a park are at K(2,5)K(2, 5) and L(8,7)L(8, 7). Which is the equation of the edge between their cells?
Check yourself
A vertex is at (4,7)(4, 7) and one of its three sites at (1,3)(1, 3), with distances in km. How far, in km, is it from the other two?

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.

Two Voronoi diagrams of the same 12 by 10 rectangle. Before: sites A, B and C with three edges meeting at vertex V at (6, 4). After adding site D at (3, 4): D gets a new shaded cell bounded by the edge x = 7 with B, the edge y = 6 with C and a sloping edge with A. The new vertices are at (7, 1) and (7, 6). V is now inside the cell of D, so it is no longer a vertex. Before After adding D (3, 4) 024681012246810 A B C V 024681012246810 A B C D old V (7, 1) (7, 6)
Adding D: A, B and C all lose area, and the old vertex VV disappears.
Worked exampleFuel stations at F(2,4)F(2, 4) and G(10,4)G(10, 4) (in km) have the edge x=6x = 6. A third opens at H(6,10)H(6, 10). Find the new edges and the new vertex.

Try it first, then reveal one step at a time.

  1. F–H: midpoint (4,7)(4, 7), gradient of FH 32\frac{3}{2}, so the edge is y−7=−23(x−4)y - 7 = -\frac{2}{3}(x - 4), or 2x+3y=292x + 3y = 29.
Worked exampleA fourth library opens at D(3,4)D(3, 4) in the map of A(2,1)A(2, 1), B(11,4)B(11, 4) and C(3,8)C(3, 8). (a) Show that D is in the cell of A. (b) Write down the edges between D and B, and between D and C. (c) Find the vertex where the cells of B, C and D meet. (d) Explain why V(6,4)V(6, 4) is no longer a vertex.

Try it first, then reveal one step at a time.

  1. (a) DA=10≈3.16DA = \sqrt{10} \approx 3.16, DB=8DB = 8 and DC=4DC = 4. DADA is the smallest.
Check yourself
A new site is added to a Voronoi diagram. Which cells can change?
Check yourself
The edge between A(2,1)A(2, 1) and D(3,4)D(3, 4) meets the line x=0x = 0 at (0,k)(0, k). Find kk to 3 s.f.

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.

Worked exampleRain gauges are at P(2,7)P(2, 7), Q(8,9)Q(8, 9) and R(6,2)R(6, 2), with distances in km. Last month they recorded 2323 mm, 3131 mm and 1717 mm. (a) Use nearest neighbour interpolation to estimate last month's rainfall at a farm at F(5,6)F(5, 6). (b) Comment on your estimate.

Try it first, then reveal one step at a time.

  1. (a) FP=32+12=10≈3.16FP = \sqrt{3^2 + 1^2} = \sqrt{10} \approx 3.16 km.

For the area of a cell, find its corners from the edges' equations. Then split it into rectangles, triangles and trapezoids.

A field drawn as a rectangle 8 units wide and 6 units tall, with sensors S at (2, 3) and T at (6, 1). A straight dashed edge runs from (3, 0) on the bottom side to (6, 6) on the top side. The cell of S, to the left of the edge, is shaded: a trapezium with parallel sides of 3 units along the bottom and 6 units along the top, 6 units apart. 012345678123456 S (2, 3) T (6, 1) edge
The cell of S is a trapezoid.
Worked exampleA field is the rectangle 0≤x≤80 \le x \le 8, 0≤y≤60 \le y \le 6, where 11 unit is 1010 m. Soil sensors are at S(2,3)S(2, 3) and T(6,1)T(6, 1). (a) Find the equation of the edge between their cells. (b) Find the area of the cell of S, in m2\text{m}^{2}.

Try it first, then reveal one step at a time.

  1. (a) Midpoint (4,2)(4, 2). Gradient of ST: 1−36−2=−12\frac{1 - 3}{6 - 2} = -\frac{1}{2}, so the edge has gradient 22: y−2=2(x−4)y - 2 = 2(x - 4), so y=2x−6y = 2x - 6.
Check yourself
Gauges P and Q recorded 2323 mm and 3131 mm. A village is in the cell of P, very close to the edge with Q. Why might its nearest neighbour estimate be poor?
Check yourself
On a park map, 11 unit is 0.40.4 km. A cell is the triangle bounded by the xx-axis, the yy-axis and the edge 4x+3y=244x + 3y = 24. Find its area in km2\text{km}^{2}, to 3 s.f.

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.

Voronoi diagram of four villages P at (4, 6), Q at (5, 11), R at (9, 11) and S at (13, 3) in a 15 by 13 rectangle. It has two vertices, U at (7, 8) and W at (9, 6). A dotted circle centred on U passes through P, Q and R, with radius about 3.6. A larger dotted circle centred on W passes through P, R and S, with radius 5. No village lies inside either circle. 0246810121424681012 P Q R S U (7, 8) W (9, 6)
No village is inside either circle, so each radius is that vertex's distance to the nearest village.
Worked exampleVillages are at P(4,6)P(4, 6), Q(5,11)Q(5, 11), R(9,11)R(9, 11) and S(13,3)S(13, 3), with distances in km. The Voronoi vertices are U(7,8)U(7, 8), shared by the cells of P, Q and R, and W(9,6)W(9, 6), shared by P, R and S. A waste dump inside PQRS must be as far as it can be from its nearest village. Find where, and that distance.

Try it first, then reveal one step at a time.

  1. The best point is a vertex, so compare UU and WW.
Worked exampleVillages are at A(4,11)A(4, 11), B(10,11)B(10, 11), C(10,5)C(10, 5) and D(5,2)D(5, 2), in km. A recycling plant inside ABCD must be as far as it can be from its nearest village. The Voronoi vertices are (7,8)(7, 8), shared by A, B and C, and a second one shared by A, C and D. (a) The edge between A and C is y=x+1y = x + 1. Find the edge between C and D. (b) Use your calculator to find the second vertex. (c) Determine where to build the plant. (d) State one limitation of this model.

Try it first, then reveal one step at a time.

  1. (a) Midpoint of C and D: (7.5,3.5)(7.5, 3.5). Gradient of CD: 2−55−10=35\frac{2 - 5}{5 - 10} = \frac{3}{5}, so the edge has gradient −53-\frac{5}{3}.
Check yourself
In an IB exam, where is the solution to a toxic waste dump problem?
Check yourself
A Voronoi diagram has two vertices: X(6,9)X(6, 9), with (2,6)(2, 6) one of its sites, and Y(10,4)Y(10, 4), with (12,9)(12, 9) one of its sites. Distances are in km. Find the largest distance, in km, to the nearest site, to 3 s.f.

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 (x,y)(x, y) 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: 11 unit =2= 2 km means 11 square unit =4 km2= 4\text{ km}^{2}.
  • 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

Learn thisEvery point inside a site's cell is closer to that site than to any other site.
Learn thisAn edge lies on the perpendicular bisector of its two sites.
Learn thisA vertex is equally far from the sites of all the cells meeting there.
Learn thisEdge: through the midpoint of two sites, with gradient −1m-\frac{1}{m} if the segment's gradient is m≠0m \neq 0 (level sites: vertical edge; one above the other: horizontal edge). Vertex: solve two edges simultaneously.
Learn thisAdding a site: draw its bisectors with neighbouring sites and erase old edges inside its new cell.
Learn thisNearest neighbour interpolation: every point in a cell gets its site's value.
Learn thisToxic waste dump problem (IB exams): compare each vertex's distance to one of its own sites; the largest wins.
Learn thisIf 11 unit is kk km on a map, 11 square unit is k2 km2k^2\text{ km}^{2}.

Practise this

12 past-paper questions on Voronoi diagrams in the AI HL bank, each with a mark scheme and a worked explanation.

Practise Voronoi diagrams →