Which town is nearest?
Two towns stand on a map: A at (1, 2) and B at (2, 7). Each home goes to the school in the nearer town, measured in a straight line. For every point of the map the question is the same: is it nearer to A or nearer to B?
One point can be settled by working out its two distances. The point P at (2, 3) is from A, and from B, so it is nearer to A. A Voronoi diagram answers the question for every point at once.
P at (2, 3) is 1.41 from A and 4 from B, so P is nearer to A.
The perpendicular bisector
The points that are equally far from A and from B form a straight line: the perpendicular bisector of AB. It passes through the midpoint of AB, (1.5, 4.5), and crosses AB at a right angle. Its equation is x + 5y = 24, and the midpoint fits it: 1.5 + 5 × 4.5 = 24.
The bisector splits the plane into two halves. Every point on A’s side is nearer to A, and every point on B’s side is nearer to B. Those two halves are the two towns’ cells.
The perpendicular bisector of AB, in gold: every point on it is the same distance from A as from B.
A’s cell, in gold, is every point of the frame nearer to A. Its corners are (0, 0), (12, 0), (12, 2.4) and (0, 4.8).
Four towns, four cells
Add C at (7, 2) and D at (10, 11). The points nearer to A than to any other town must be on A’s side of three bisectors at once: the bisectors of AB, AC and AD. A’s cell is the region inside all three halves. Every town’s cell is found in the same way, and together the cells fill the map without overlapping.
This division of the plane into cells, one for each town, is the Voronoi diagram of the towns. The towns are its sites. Every point in a site’s cell is nearer to that site than to any other site.
C’s cell has corners (4, 0), (12, 0), , (7, 7) and (4, 4). Its left side lies on x = 4, the bisector of A and C, which are level with each other, and its top edges lie on the bisectors of C with B and of C with D.
The Voronoi diagram of the four towns, with C’s cell in gold: every point in it is nearer to C than to A, B or D.
Edges and vertices
Each edge of a cell is a piece of a perpendicular bisector: the part where those two sites are equally near and no other site is nearer. Two sites whose cells share an edge are neighbors.
A vertex is a point where three cells meet, so it is equally far from three sites. The vertex (4, 4) is from A, B and C, and D is from it, farther away. The other vertex, (7, 7), is exactly 5 from B, C and D, and A is from it.
Not every pair of sites are neighbors. A and D are the farthest apart, and their cells never touch: the cells of B and C lie between them.
The vertex V at (4, 4) is 3.61 from each of A, B and C: the cells of A, B and C meet there.
The vertex V at (7, 7) is 5 from each of B, C and D: the cells of B, C and D meet there.
Reading the nearest site
Once the diagram is drawn, the nearest site to any point is read from the cell the point lies in, with no distances to compare. The point (8, 4) lies in C’s cell. Checking with squared distances: it is from A, from B, from C and from D, so C is nearest.
Drag the gold tower P below. Its cell changes shape, and each wall of the cell lies on the perpendicular bisector of P and one of the fixed towers.
each wall of P's cell is the perpendicular bisector of P and one tower — |x − P| = |x − S| on it, |x − P| < |x − S| inside — and the cell touches 4 of the 4
Drag P until it is the same distance from its two nearest towers
Four fixed towers, A, B, C and D, and a fifth, P, that moves. At (1.4, 2.5), P’s cell has 4 walls, one against each tower, and the nearest tower is D, 1.40 away.
The usual mistakes
Drawing the line through the two sites as the boundary. Its points run toward one site and away from the other. The boundary is the perpendicular bisector, which crosses that line at its midpoint at a right angle.
Expecting every pair of sites to share an edge. A and D do not.
Taking any point equally far from three sites as a vertex. It is a vertex only when no other site is nearer to it; the first application below has a point equally far from three masts with the fourth mast closer.
Using one bisector alone to decide a cell. Being nearer to A than to B is not enough; a point in A’s cell is nearer to A than to every other site.
Masts and recycling centers
In the first application below, four cell phone masts divide a valley, and a passenger’s phone is handed from mast to mast along a railway. In the second, a new recycling center takes area from the cells of the existing ones.
Worked example: Four Cell Phone Masts in a Valley: Which Cells Share an Edge, and the Handovers Along a Railway
Question 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.
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.
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. 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.
D is only √5 from (7, 6), inside the circle, so (7, 6) is nearer D than A, B or C and is not a vertex. 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).
The bisector of AD, x + y = 10, meets x = 7 at (7, 3) and y = 6 at (4, 6): the two vertices. 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.
(a) The edge A–D joins the two vertices. The other edges run from them to the boundary, and none joins B to C. 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.
Along y = 4 the phone leaves A's cell at x = 6 and leaves D's cell at x = 8.5, where 2x − 3y = 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.
(b) A from (0, 4), D from (6, 4), and B from (8.5, 4) to (13, 4).
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)
Common mistakes
- 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.
Worked example: A New Recycling Center in a City: Its Cell, and How Much Area It Takes from Each Existing Center
Question 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?
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.
N's cell lies on N's side of its bisectors with C, x + y = 14, and with B, 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.
The bisector with A, x + y = 10, lies wholly on N's side of x + y = 14, so it forms no edge of 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).
(a) The corners of N's cell are (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².
The old edge between B and C, y = x − 4, cuts off a triangle of 3 km² that was B's. 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.
The shoelace formula gives N's cell 26 km², so 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.
(b) B loses 3 km² and C loses 23 km². A's cell, where x + y ≤ 8, never meets N's.
Answer: (a) (9, 5), (12, 6), (12, 10) and (4, 10). (b) B loses 3 km² and C loses 23 km²; A loses none
Common mistakes
- 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.