Voronoi Diagrams · applications

Applications: Voronoi Diagrams

10 question types · Pre-University · each worked step by step with a figure that follows the steps

01

Four Cell Phone Masts in a Valley: Which Cells Share an Edge, and the Handovers Along a Railway

methodTest Whether the Fourth Mast Lies Inside the Circle Through the Other Three, Find the Vertices, Then Walk Along the Railway and Note Where It Crosses an Edge

Four cell phone masts stand in a valley that is the rectangle 0 ≤ x ≤ 13, 0 ≤ y ≤ 12, with distances in kilometers: A at (2, 2), B at (12, 2), C at (2, 10) and D at (8, 8). Model each phone as connecting to the nearest mast, so that each mast serves its Voronoi cell, and a phone that crosses the edge between two cells is handed over directly from one mast to the other. (a) Which pairs of masts have cells that share an edge, and which pair do not? (b) A railway runs straight along the line y = 4 from (0, 4) to (13, 4). List the masts a passenger's phone is connected to, in order from west to east, and give the point where each handover happens.

48124812ABCD(7, 6)circle through A, B and C: center (7, 6), radius √41
The circle through A, B and C has its center on x = 7 and on y = 6: the center is (7, 6) and the radius is √41.
The masts are the corners of the quadrilateral ABDC, with A and D on one diagonal and B and C on the other. Test the circle through A, B and C. Its center is equally far from A and B, so it lies on x = 7, and equally far from A and C, so it lies on y = 6. The center is (7, 6), and the radius is √52 + 42 = √41.
step 1 of 6

Two masts share an edge when there are points equally near to both and nearer to them than to any other mast. The vertices of the diagram are the centers of circles through three masts with no fourth mast inside, and the edges run between the vertices along perpendicular bisectors.

  1. The masts are the corners of the quadrilateral ABDC, with A and D on one diagonal and B and C on the other. Test the circle through A, B and C. Its center is equally far from A and B, so it lies on x = 7, and equally far from A and C, so it lies on y = 6. The center is (7, 6), and the radius is √52 + 42 = √41.
  2. D is √12 + 22 = √5 from (7, 6), which is less than √41, so D is inside that circle and nearer to (7, 6) than A, B and C are. So (7, 6) is not a vertex, and the vertices are the centers of the circles through A, B, D and through A, C, D.
  3. The perpendicular bisector of AD passes through the midpoint (5, 5) with gradient −1, so it is x + y = 10. It meets x = 7 at (7, 3), which is √26 from A, B and D, and it meets y = 6 at (4, 6), which is √20 from A, C and D. Neither circle holds the fourth mast: C is √74 from (7, 3), and B is √80 from (4, 6).
  4. (a) The edge between A and D joins (4, 6) to (7, 3). From (7, 3) the edge between A and B runs down x = 7 and the edge between B and D runs to the east boundary; from (4, 6) the edge between A and C runs west along y = 6 and the edge between C and D runs to the north boundary. So A–B, A–C, A–D, B–D and C–D share edges, and B and C do not.
  5. (b) The phone starts in A's cell at (0, 4). The edge between A and D, x + y = 10, crosses y = 4 at x = 6, and y = 4 lies between the ends of that edge, y = 3 and y = 6. The edge between B and D has midpoint (10, 5), and BD has gradient 6−4 = −32, so the edge has gradient 23: y − 5 = 23(x − 10), which is 2x − 3y = 5. At y = 4, 2x = 17 and x = 8.5.
  6. (b) The phone is connected to A from (0, 4) to (6, 4), to D from (6, 4) to (8.5, 4), and to B from (8.5, 4) to (13, 4). The edge between A and B stops at (7, 3), below the railway, so the phone is never handed straight from A to B. Check: (6, 4) is √20 from both A and D, and (8.5, 4) is √16.25 from both D and B.

answer(a) A–B, A–C, A–D, B–D and C–D share edges; B and C do not. (b) A, then D from (6, 4), then B from (8.5, 4)

techniqueVoronoi Diagrams · The Equation of a Voronoi Edge

Common pitfalls

  • Taking (7, 6), the point equally far from A, B and C, as a vertex. D is only √5 from it, nearer than A, B or C, so no point near (7, 6) is served by any of those three masts, and the cells of B and C never meet.
  • Handing the phone from A straight to B at x = 7, where the edge between A and B lies. That edge ends at the vertex (7, 3), below the railway, so along y = 4 the phone passes through D's cell between x = 6 and x = 8.5.
02

A New Recycling Center in a City: Its Cell, and How Much Area It Takes from Each Existing Center

methodDraw the Perpendicular Bisector Between the New Center and Each Existing One, Keep the Side Nearer the New Center, Then Split the New Cell Along the Old Edges

A city is the rectangle 0 ≤ x ≤ 12, 0 ≤ y ≤ 10, in kilometers. Its three recycling centers are A at (2, 2), B at (10, 2) and C at (6, 6), and each home is assigned to the nearest center by straight-line distance. A fourth center, N, opens at (8, 8). (a) Find the corners of N's Voronoi cell inside the city. (b) Which of A, B and C lose area to N, and how many square kilometers does each lose?

481248ABCNwith C: x + y = 14with B: x − 3y = −6
N's cell lies on N's side of its bisectors with C, x + y = 14, and with B, x − 3y = −6.
Between N and C: the midpoint is (7, 7) and NC has gradient 1, so the bisector has gradient −1 and is x + y = 14. Between N and B: the midpoint is (9, 5) and NB has gradient 6−2 = −3, so the bisector has gradient 13: y − 5 = 13(x − 9), which is x − 3y = −6. N's cell is where x + y ≥ 14 and x − 3y ≤ −6.
step 1 of 6

N's cell is the part of the city nearer N than any other center, so it is cut out by the perpendicular bisectors between N and each existing center. Each piece of that cell was taken from the center whose old cell it lay in, and the old edges show where one piece ends and the next begins.

  1. Between N and C: the midpoint is (7, 7) and NC has gradient 1, so the bisector has gradient −1 and is x + y = 14. Between N and B: the midpoint is (9, 5) and NB has gradient 6−2 = −3, so the bisector has gradient 13: y − 5 = 13(x − 9), which is x − 3y = −6. N's cell is where x + y ≥ 14 and x − 3y ≤ −6.
  2. Between N and A: the midpoint is (5, 5), so the bisector is x + y = 10. Every point with x + y ≥ 14 also has x + y > 10, so it is already nearer N than A, and this bisector does not bound N's cell.
  3. (a) The two bisectors meet where x + y = 14 and x − 3y = −6. Subtracting gives 4y = 20, so y = 5 and x = 9. The line x − 3y = −6 meets the east boundary x = 12 at y = 6, and x + y = 14 meets the north boundary y = 10 at x = 4. N's cell has corners (9, 5), (12, 6), (12, 10) and (4, 10).
  4. Before N opened, the edge between B and C was their perpendicular bisector, y = x − 4, which passes through (9, 5) and meets x = 12 at (12, 8). The part of N's cell below that line was B's: the triangle (9, 5), (12, 6), (12, 8), with base 2 along x = 12 and height 12 − 9 = 3, so its area is 12 × 2 × 3 = 3 km².
  5. The whole of N's cell, by the shoelace formula with its corners in order (9, 5), (12, 6), (12, 10), (4, 10): 12 |(54 − 60) + (120 − 72) + (120 − 40) + (20 − 90)| = 12 × 52 = 26 km². The rest of it, 26 − 3 = 23 km², was C's.
  6. (b) B loses 3 km² and C loses 23 km². A loses nothing: A's cell is nearer A than C, which means x + y ≤ 8, and every point of N's cell has x + y ≥ 14. Check: 3 + 23 = 26, the area of N's cell.

answer(a) (9, 5), (12, 6), (12, 10) and (4, 10). (b) B loses 3 km² and C loses 23 km²; A loses none

techniqueVoronoi Diagrams · The Area of a Voronoi Cell

Common pitfalls

  • Expecting every existing center to lose some area to N. A's cell lies where x + y ≤ 8 and N's cell lies where x + y ≥ 14, so no home that used A is nearer N.
  • Counting all of N's cell as C's loss because C is the center nearest to N. The old edge between B and C, y = x − 4, cuts through N's cell, and the triangle below it, 3 km², came from B.
03

The Zone Boundary Between Two Elementary Schools, and Where a Straight Road Crosses It

methodFind the Midpoint of the Two Schools and the Negative Reciprocal of the Gradient Between Them, Write the Boundary as y = mx + c, Then Substitute the Road's Equation

A town plans to zone each home to the nearer of its two elementary schools by straight-line distance. On the town map, in kilometers, school A is at (1, 2) and school B is at (7, 6). (a) Find the equation of the zone boundary in the form y = mx + c. (b) A straight road runs along y = 1. At what point on the road does the zone change, and to which school are the homes on the road east of that point zoned?

2468246AB(4, 4)midpoint of AB: (4, 4)
The boundary passes through the midpoint of AB, (4, 4).
The midpoint of AB is (1 + 72, 2 + 62) = (4, 4).
step 1 of 5

Every point on the boundary is equally far from the two schools, so the boundary is the perpendicular bisector of AB: it passes through the midpoint of AB at right angles to AB.

  1. The midpoint of AB is (1 + 72, 2 + 62) = (4, 4).
  2. The gradient of AB is 6 − 27 − 1 = 46 = 23. The boundary is perpendicular to AB, so its gradient is the negative reciprocal, −32. Check: 23 × (−32) = −1.
  3. (a) The line through (4, 4) with gradient −32 is y − 4 = −32(x − 4), so y = −32x + 6 + 4, which is y = −32x + 10.
  4. Substitute the road, y = 1: 1 = −32x + 10, so 32x = 9 and x = 6. The zone changes at (6, 1). Check: (6, 1) is √52 + 12 = √26 km from A and √12 + 52 = √26 km from B.
  5. (b) Test a home east of that point, at (8, 1): it is √72 + 12 = √50 km from A and √12 + 52 = √26 km from B, so it is nearer B. The homes on the road east of (6, 1) are zoned to B, even though A is only 1 km from the road and B is 5 km from it.

answer(a) y = −32x + 10. (b) At (6, 1); the homes east of it are zoned to B

techniqueThe Equation of a Voronoi Edge

Common pitfalls

  • Using the gradient of AB, 23, for the boundary. That line runs through the midpoint parallel to AB; the boundary crosses AB at a right angle, so its gradient is −32.
  • Zoning the homes east of (6, 1) to A because A is only 1 km from the road. Each home compares its own two distances, and (8, 1) is √50 km from A but only √26 km from B.
04

Three Fire Stations in a County: Two Edges Between Their Response Areas, and the Point Where They Meet

methodWrite Each Edge as a Perpendicular Bisector in the Form ax + by = c, Solve the Two Equations Together, Then Check the Point on the Third Bisector

A county is the rectangle 0 ≤ x ≤ 14, 0 ≤ y ≤ 14, in kilometers, and its fire stations are A at (1, 1), B at (13, 7) and C at (5, 13). A first plan sends each call to the nearest station by straight-line distance. (a) Find the equations of the edge between A's and B's areas and of the edge between B's and C's areas, each in the form ax + by = c with whole numbers. (b) Find the point where the two edges meet, and its straight-line distance from each station.

48124812ABC(7, 4)AB: midpoint (7, 4), gradient 1/2edge: gradient −2, so 2x + y = 18
The edge between A and B passes through (7, 4) with gradient −2: 2x + y = 18.
The edge between A and B: the midpoint of AB is (7, 4) and AB has gradient 612 = 12, so the edge has gradient −2: y − 4 = −2(x − 7), which is 2x + y = 18.
step 1 of 6

The edge between two stations' areas is the perpendicular bisector of the line joining them. Where two edges meet, the point is equally far from all three stations, so it must lie on the third bisector too, which checks the working.

  1. The edge between A and B: the midpoint of AB is (7, 4) and AB has gradient 612 = 12, so the edge has gradient −2: y − 4 = −2(x − 7), which is 2x + y = 18.
  2. The edge between B and C: the midpoint of BC is (9, 10) and BC has gradient 13 − 75 − 13 = −34, so the edge has gradient 43: y − 10 = 43(x − 9). Multiply both sides by 3: 3y − 30 = 4x − 36, which is 4x − 3y = 6.
  3. (a) The edges are 2x + y = 18 and 4x − 3y = 6.
  4. Solve them together. Multiply the first equation by 3: 6x + 3y = 54. Add the second: 10x = 60, so x = 6, and y = 18 − 12 = 6. The edges meet at (6, 6).
  5. The distance from (6, 6) to A is √52 + 52 = √50, to B is √72 + 12 = √50, and to C is √12 + 72 = √50.
  6. (b) The edges meet at (6, 6), which is √50 = 5√2 ≈ 7.07 km from each station. Check on the third edge, between A and C: its midpoint is (3, 7) and its gradient is −13, which gives x + 3y = 24, and 6 + 3 × 6 = 24.

answer(a) 2x + y = 18 and 4x − 3y = 6. (b) (6, 6), 5√2 ≈ 7.07 km from each station

techniqueThe Equation of a Voronoi Edge · Voronoi Diagrams

Common pitfalls

  • Writing the edge through the midpoint with the gradient of AB, y − 4 = 12(x − 7). That line is parallel to AB; the edge crosses AB at a right angle, so its gradient is −2.
  • Leaving the edge as y − 10 = 43(x − 9) when whole numbers are asked for. Multiplying both sides by 3 clears the fraction and gives 4x − 3y = 6.
05

Sending the Nearest Ambulance: a Caller Inside One Station's Cell, and a Caller on an Edge

methodCompare the Squares of the Straight-Line Distances to Every Station; Where the Two Smallest Are Equal, the Caller Is on the Edge Between Those Two Cells

An ambulance service covers the rectangle 0 ≤ x ≤ 10, 0 ≤ y ≤ 12, in kilometers, from three stations: A at (1, 2), B at (9, 2) and C at (5, 10). The dispatcher's first estimate of the nearest station uses straight-line distance, before road travel times are checked. (a) A call comes from (4, 6). Which station is nearest, and how far away is it? (b) A second call comes from (9, 7). Show that this caller is on an edge of the Voronoi diagram of the stations, name the two stations the caller is equally far from, and give that distance.

24684812ABC(4, 6)from (4, 6): A 25, B 41, C 17 (squared)
The squared distances from (4, 6) are 25 to A, 41 to B and 17 to C.
From (4, 6), the squared distances are: to A, 32 + 42 = 25; to B, 52 + 42 = 41; to C, 12 + 42 = 17.
step 1 of 5

The nearest station is the one with the smallest distance, and comparing the squares of the distances puts the stations in the same order without taking roots. A caller whose two smallest distances are equal is on the edge between those two stations' cells.

  1. From (4, 6), the squared distances are: to A, 32 + 42 = 25; to B, 52 + 42 = 41; to C, 12 + 42 = 17.
  2. (a) C is nearest, at √17 ≈ 4.12 km. A is exactly 5 km away, which is farther, because 17 < 25.
  3. From (9, 7): to A, 82 + 52 = 89; to B, 02 + 52 = 25; to C, 42 + 32 = 25. The two smallest are equal, so the caller is √25 = 5 km from both B and C, and A is farther.
  4. Check against the edge between B and C, their perpendicular bisector. The midpoint of BC is (7, 6) and BC has gradient 8−4 = −2, so the edge has gradient 12: y = 12x + 52. At x = 9, y = 4.5 + 2.5 = 7, so (9, 7) is on it.
  5. (b) The caller at (9, 7) is on the edge between the cells of B and C, 5 km from each. By straight-line distance neither station is nearer, so the dispatcher decides between B and C on the road travel times.

answer(a) C, at √17 ≈ 4.12 km. (b) The caller is on the edge between the cells of B and C, 5 km from each

techniqueFinding the Nearest Site

Common pitfalls

  • Stopping at A because the distance to it comes out as exactly 5 km. Every station must be checked, and the squared distance to C, 17, is smaller than 25.
  • Sending the call from (9, 7) to B because B has the same x-coordinate. B and C are both 5 km away, so the caller is on the edge between their cells, and the map alone does not choose between them.
06

A Supermarket That Will Close: Which Stores Take Over Its Customers, and One Customer's New Nearest Store

methodBuild the Closing Store's Cell from the Perpendicular Bisectors, Read Off the Stores Whose Bisectors Form Its Edges, Then Compare the Customer's Distances to the Stores That Remain

A supermarket chain has five stores in a city that is the rectangle 0 ≤ x ≤ 12, 0 ≤ y ≤ 10, in kilometers: P at (6, 5), A at (2, 1), B at (9, 2), C at (10, 9) and D at (12, 1). The chain counts each customer as belonging to the nearest store by straight-line distance. Store P will close. (a) Which stores have cells that share an edge with P's cell, and so take over P's customers, and which store takes over none? (b) A customer lives at (2, 8). How far is she from P, which store is nearest to her once P closes, and how much farther away is it?

4848PABCDwith A: x + y = 7with B: x − y = 4
The bisectors of P with A and with B: x + y = 7 and x − y = 4.
With A: the midpoint is (4, 3) and PA has gradient 1, so the bisector is x + y = 7. With B: the midpoint is (7.5, 3.5) and PB has gradient −1, so the bisector is x − y = 4.
step 1 of 6

P's cell is the part of the city nearer P than each other store, so it is bounded by the perpendicular bisectors between P and the others. A store whose bisector with P forms an edge of the cell borders P's customers; a store whose bisector lies wholly outside the cell does not.

  1. With A: the midpoint is (4, 3) and PA has gradient 1, so the bisector is x + y = 7. With B: the midpoint is (7.5, 3.5) and PB has gradient −1, so the bisector is x − y = 4.
  2. With C: the midpoint is (8, 7) and PC has gradient 1, so the bisector is x + y = 15. With D: the midpoint is (9, 3) and PD has gradient −23, so the bisector has gradient 32: y − 3 = 32(x − 9), which is 3x − 2y = 21.
  3. P's side of each line is the side that holds P: x + y ≥ 7, x − y ≤ 4, x + y ≤ 15 and 3x − 2y ≤ 21. The first three lines and the city's boundary give the corners (0, 7), then (5.5, 1.5) where x + y = 7 meets x − y = 4, then (9.5, 5.5) where x − y = 4 meets x + y = 15, then (5, 10) where x + y = 15 meets the north boundary, and the corner (0, 10).
  4. At those corners 3x − 2y is −14, 13.5, 17.5, −5 and −20, all less than 21, so the whole cell is on P's side of the bisector with D, and that bisector forms no edge. (a) A, B and C share edges with P's cell and take over its customers; D takes over none.
  5. The customer at (2, 8) is in P's cell: 2 + 8 = 10 lies between 7 and 15, and 2 − 8 = −6 is less than 4. She is √42 + 32 = 5 km from P.
  6. Once P closes, her distances are: to A, √02 + 72 = 7 km; to B, √72 + 62 = √85 km; to C, √82 + 12 = √65 km; to D, √102 + 72 = √149 km. (b) She is 5 km from P, and A is now nearest, at 7 km, which is 7 − 5 = 2 km farther.

answer(a) A, B and C; D takes over none. (b) She is 5 km from P; once P closes, A is nearest, at 7 km, which is 2 km farther

techniqueFinding the Nearest Site · Voronoi Diagrams · The Equation of a Voronoi Edge

Common pitfalls

  • Counting D because it is one of the four stores around P. The bisector between P and D, 3x − 2y = 21, stays outside P's cell at every corner, so D's cell does not touch P's cell.
  • Answering (b) with the new distance alone, 7 km. The question also asks how much farther the new store is than P, which is 7 − 5 = 2 km.
07

A Landfill Site in a County with Three Towns: the Point Equally Far from All Three, and the Point Farthest from Every Town

methodFind the Voronoi Vertex as the Center of the Circle Through the Three Towns, Then Compare It with Every Corner of the County and Every Point Where an Edge Meets the Boundary

A county is the rectangle 0 ≤ x ≤ 18, 0 ≤ y ≤ 14, in kilometers, with three towns: A at (4, 4), B at (12, 4) and C at (8, 12). The county wants a site for a landfill as far as possible from the nearest town, by straight-line distance. (a) Find the point equally far from all three towns, and that distance. (b) Find the point of the county that is farthest from its nearest town, and that distance.

4812164812ABCA and B: x = 8; A and C: x + 2y = 22
The bisectors of A and B, x = 8, and of A and C, x + 2y = 22.
The point equally far from A and B is on their perpendicular bisector, x = 8. For A and C, the midpoint of AC is (6, 8) and AC has gradient 2, so the bisector is y − 8 = −12(x − 6), which is x + 2y = 22.
step 1 of 6

Inside one Voronoi cell the distance to the nearest town is the distance to that cell's own town, and over the cell it is greatest at one of the cell's corners. So the farthest point from every town is a vertex of the diagram, a corner of the county, or a point where an edge meets the boundary, and each candidate is compared.

  1. The point equally far from A and B is on their perpendicular bisector, x = 8. For A and C, the midpoint of AC is (6, 8) and AC has gradient 2, so the bisector is y − 8 = −12(x − 6), which is x + 2y = 22.
  2. (a) At x = 8, 2y = 14 and y = 7. The point (8, 7) is √42 + 32 = 5 km from A, from B and from C.
  3. The edge between A and B, x = 8, meets the south boundary at (8, 0), which is √32 ≈ 5.66 km from A and from B. The edge between A and C meets the west boundary x = 0 at (0, 11), which is √65 ≈ 8.06 km from A and from C.
  4. The edge between B and C: the midpoint of BC is (10, 8) and BC has gradient −2, so the bisector is y − 8 = 12(x − 10), which is x − 2y = −6. It meets the east boundary x = 18 at (18, 12), which is √62 + 82 = 10 km from B and from C.
  5. The corners: (0, 0) is √32 km from A, its nearest town; (18, 0) is √52 km from B; (0, 14) is √68 km from C; and (18, 14) is √102 + 22 = √104 km from C, which is nearer to it than B at √136 km.
  6. (b) The largest of these is √104 = 2√26 ≈ 10.2 km, at the corner (18, 14). It beats the 10 km at (18, 12) and is about twice the 5 km at the vertex.

answer(a) (8, 7), 5 km from each town. (b) The corner (18, 14), 2√26 ≈ 10.2 km from C, its nearest town

techniqueThe Toxic Waste Dump Problem

Common pitfalls

  • Taking the vertex (8, 7) as the answer to (b). It is only 5 km from each town; the corners of the county and the points where edges meet the boundary must be compared too, and the corner (18, 14) is about 10.2 km from its nearest town.
  • Measuring a corner's distance to the wrong town. (18, 14) is √136 km from B, but its nearest town is C, at √104 km, and the nearest town is the one that counts.
08

A Fireworks Storage Depot in a District with Four Villages, and the Best Site Again After a New Village Is Planned

methodList Every Candidate, the Voronoi Vertices, the Corners and the Points Where Edges Meet the Boundary, Find Each One's Distance to Its Nearest Village, and Take the Largest

A district is the rectangle 0 ≤ x ≤ 16, 0 ≤ y ≤ 12, in kilometers, with four villages: A at (1, 1), B at (13, 1), C at (4, 10) and D at (13, 10). A fireworks storage depot is to be built as far as possible from the nearest village, by straight-line distance. (a) Find the site in the district that is farthest from its nearest village, and that distance. (b) Before building starts, a new village N is planned at (7, 10). Find the new best site and its distance from the nearest village.

4812164812ABCD(7, 4)A, B, C: x = 7 and x + 3y = 19, so (7, 4)√45 from A, B and C; D is √72
The vertex for A, B and C is (7, 4), √45 km from each of them.
The vertex for A, B and C: equally far from A and B means x = 7. Equally far from A and C means (x − 1)2 + (y − 1)2 = (x − 4)2 + (y − 10)2, which simplifies to x + 3y = 19. At x = 7, y = 4: the point (7, 4) is √62 + 32 = √45 km from A, B and C, and D is farther, at √72 km.
step 1 of 6

The best site is a vertex of the Voronoi diagram, a corner of the district, or a point where an edge meets the boundary. Each candidate is measured to its nearest village, and a new village means a new diagram, so the list is made again.

  1. The vertex for A, B and C: equally far from A and B means x = 7. Equally far from A and C means (x − 1)2 + (y − 1)2 = (x − 4)2 + (y − 10)2, which simplifies to x + 3y = 19. At x = 7, y = 4: the point (7, 4) is √62 + 32 = √45 km from A, B and C, and D is farther, at √72 km.
  2. The vertex for B, C and D: equally far from B and D means y = 5.5, and equally far from C and D means x = 8.5. The point (8.5, 5.5) is √4.52 + 4.52 = √40.5 ≈ 6.36 km from B, C and D, and A is farther.
  3. On the boundary, the edge between A and B, x = 7, meets the south side at (7, 0), which is √37 ≈ 6.08 km from A and B. The other edges meet the boundary at (0, 193), (16, 5.5) and (8.5, 12), each less than 5.5 km from its nearest village, and every corner is within 4.5 km of a village.
  4. (a) The largest distance is at the vertex (7, 4): √45 = 3√5 ≈ 6.71 km from A, B and C.
  5. N at (7, 10) is only 6 km from (7, 4), so that site is now 6 km from its nearest village. The new vertex for A, B and N is on x = 7 and equally far from A and N: 62 + (y − 1)2 = (y − 10)2, so 37 − 2y = 100 − 20y, 18y = 63 and y = 3.5. The point (7, 3.5) is √62 + 2.52 = 6.5 km from A, B and N, and C and D are farther.
  6. (b) The other new vertices are nearer a village: (5.5, 4.5), for A, C and N, is about 5.70 km from them, and (10, 5.5), for B, D and N, about 5.41 km. The edges round N meet the north boundary at (5.5, 12) and (10, 12), only 2.5 km and about 3.61 km from N, and (7, 0) stays at 6.08 km. The new best site is (7, 3.5), 6.5 km from its nearest villages, A, B and N.

answer(a) (7, 4), 3√5 ≈ 6.71 km from A, B and C. (b) (7, 3.5), 6.5 km from A, B and N

techniqueThe Toxic Waste Dump Problem · Voronoi Diagrams

Common pitfalls

  • Stopping at the first vertex found. (8.5, 5.5) is also a vertex, and (7, 0) on the boundary is over 6 km from A and B; only a comparison of every candidate shows that (7, 4) is the farthest.
  • Keeping (7, 4) after N is planned because it is still √45 km from A, B and C. Its nearest village is now N, only 6 km away, so the candidates must be worked out again with N included.
09

The Catchment Area of a Store in a Town with Three Stores, and the Share of the Town Each Store Serves

methodFind the Corners of Each Cell from the Perpendicular Bisectors and the Town's Boundary, Use the Shoelace Formula or Trapezoids for the Areas, Then Divide by the Town's Area

A town is the rectangle 0 ≤ x ≤ 12, 0 ≤ y ≤ 10, in kilometers, with three stores of one chain: A at (1, 2), B at (5, 8) and C at (11, 2). The chain takes each store's catchment to be the part of the town nearer to it than to the other two stores. (a) Find the area of B's catchment. (b) What percentage of the town's area does each store's catchment cover?

481248ABC(6, 3)A–C: x = 6; A–B: 2x + 3y = 21; B–C: y = x − 3all three meet at (6, 3)
The three bisectors meet at (6, 3).
The edge between A and C is x = 6. The edge between A and B: the midpoint is (3, 5) and AB has gradient 64 = 32, so the edge has gradient −23: y − 5 = −23(x − 3), which is 2x + 3y = 21. The edge between B and C: the midpoint is (8, 5) and BC has gradient −1, so the edge is y = x − 3.
step 1 of 5

Each catchment is a Voronoi cell cut off by the town's boundary. Its corners are the vertex where the three edges meet and the points where edges reach the boundary; with the corners known, the area is a shoelace sum or a sum of simple shapes.

  1. The edge between A and C is x = 6. The edge between A and B: the midpoint is (3, 5) and AB has gradient 64 = 32, so the edge has gradient −23: y − 5 = −23(x − 3), which is 2x + 3y = 21. The edge between B and C: the midpoint is (8, 5) and BC has gradient −1, so the edge is y = x − 3.
  2. The three edges meet at (6, 3): 2 × 6 + 3 × 3 = 21 and 3 = 6 − 3. From there, 2x + 3y = 21 runs to the west boundary at (0, 7), and y = x − 3 runs to the east boundary at (12, 9). B's catchment has corners (0, 7), (6, 3), (12, 9), (12, 10) and (0, 10).
  3. (a) With the corners in that order, the shoelace products are 0 × 3 − 6 × 7 = −42, 6 × 9 − 12 × 3 = 18, 12 × 10 − 12 × 9 = 12, 12 × 10 − 0 × 10 = 120 and 0 × 7 − 0 × 10 = 0. The area is 12(−42 + 18 + 12 + 120 + 0) = 54 km².
  4. A's catchment is the trapezoid (0, 0), (6, 0), (6, 3), (0, 7), with parallel sides 7 and 3 that are 6 apart: 12(7 + 3) × 6 = 30 km². C's is the trapezoid (6, 0), (12, 0), (12, 9), (6, 3): 12(3 + 9) × 6 = 36 km². Check: 54 + 30 + 36 = 120 = 12 × 10.
  5. (b) As shares of the town's 120 km²: A covers 30120 = 25%, B covers 54120 = 45% and C covers 36120 = 30%.

answer(a) 54 km². (b) A 25%, B 45%, C 30%

techniqueThe Area of a Voronoi Cell

Common pitfalls

  • Drawing the edge between A and B through (3, 5) with the gradient of AB, 32. The edge is perpendicular to AB, with gradient −23; with the wrong gradient the three edges no longer meet at one point.
  • Taking the shoelace products with the corners out of order. The corners must be listed in order round the cell, or the sum no longer measures its area; the check 54 + 30 + 36 = 120 catches the slip.
10

Rainfall over a River Catchment from Three Rain Gauges, Weighted by the Area Nearest Each Gauge

methodSplit the Catchment into the Voronoi Cells of the Gauges, Find Each Cell's Area, Then Weight Each Reading by Its Cell's Area and Divide by the Whole Area

A river's catchment is modeled as the rectangle 0 ≤ x ≤ 16, 0 ≤ y ≤ 10, in kilometers, with three rain gauges: A at (1, 3), B at (7, 3) and C at (7, 9). After a storm they record 30 mm, 20 mm and 40 mm. Hydrologists estimate the average rainfall over the catchment by giving each gauge's reading to the part of the catchment nearest that gauge, which is the Thiessen polygon method. (a) Find the area of each gauge's cell. (b) Find the estimated average rainfall over the catchment, and compare it with the plain mean of the three readings.

48121648ABC(4, 6)A–B: x = 4; B–C: y = 6; A–C: x + y = 10all meet at (4, 6), √18 km from each gauge
The edges x = 4, y = 6 and x + y = 10 meet at (4, 6).
The edge between A and B is x = 4, and the edge between B and C is y = 6. For A and C, the midpoint is (4, 6) and AC has gradient 1, so the edge is x + y = 10. All three edges meet at (4, 6), which is √18 km from each gauge.
step 1 of 6

Each gauge stands for its Voronoi cell. The estimate is a weighted mean: each reading counts in proportion to the area of its cell, and the weighted total is divided by the whole area.

  1. The edge between A and B is x = 4, and the edge between B and C is y = 6. For A and C, the midpoint is (4, 6) and AC has gradient 1, so the edge is x + y = 10. All three edges meet at (4, 6), which is √18 km from each gauge.
  2. B's cell is the rectangle with corners (4, 0), (16, 0), (16, 6) and (4, 6), so its area is 12 × 6 = 72 km².
  3. A's cell has corners (0, 0), (4, 0), (4, 6) and (0, 10): a trapezoid with parallel sides 10 and 6 that are 4 apart, so its area is 12(10 + 6) × 4 = 32 km². C's cell has corners (4, 6), (16, 6), (16, 10) and (0, 10): a trapezoid with parallel sides 12 and 16 that are 4 apart, so its area is 12(12 + 16) × 4 = 56 km².
  4. (a) The cells are 32 km² for A, 72 km² for B and 56 km² for C. Check: 32 + 72 + 56 = 160 = 16 × 10.
  5. Weight each reading by its cell's area and divide by the whole area: 32 × 30 + 72 × 20 + 56 × 40160 = 960 + 1440 + 2240160 = 4640160 = 29 mm.
  6. (b) The estimate is 29 mm, which is 1 mm less than the plain mean, 30 + 20 + 403 = 30 mm. It is lower because B, with the lowest reading, stands for the largest cell.

answer(a) A 32 km², B 72 km², C 56 km². (b) 29 mm, which is 1 mm less than the plain mean of 30 mm

techniqueThe Area of a Voronoi Cell

Common pitfalls

  • Averaging the three readings to get 30 mm. That counts every gauge as standing for the same area, but B's cell is 72 km² and A's is only 32 km².
  • Dividing the weighted total, 4640, by 3 instead of by the whole area, 160 km². The weights are areas, so the total is divided by the sum of the areas.
Mr. Chalk Read the guide