Read the cell
Four towns stand on a map: A at (1, 2), B at (2, 7), C at (7, 2) and D at (10, 11). Their Voronoi diagram splits the map into four cells, and every point in a town’s cell is nearer to that town than to any other.
The point P at (8, 4) lies inside the cell of C, whose corners are (4, 0), (12, 0), , (7, 7) and (4, 4). So C is the nearest town to P. Once the diagram is drawn, the nearest town to any point is read from the cell the point is in.
P at (8, 4) lies in the cell of C, in gold, so C is the nearest town to P.
Check by measuring
The cell can be checked by working out all four distances. Comparing squared distances is enough, because the larger distance always has the larger square, so no square roots are needed.
From P at (8, 4), the squared distances are to A, to B, to C and to D. The smallest is 5, so C is nearest, at . The others are to B and to both A and D.
The distances from P: 7.28 to A, 6.71 to B, 2.24 to C and 7.28 to D. The distance to C is the smallest.
A point on an edge
A point on an edge of the diagram has two nearest towns. The point (4, 2) is on the edge between the cells of A and C, which lies on the line x = 4. Its squared distances are to A and to C, so it is 3 from each. B is away and D is away, both farther.
For a point on an edge, measuring cannot pick one town. The two smallest distances are equal, and the point is equally near both.
Q at (4, 2) is on the edge between the cells of A and C, 3 from each.
Nearest-site interpolation
Suppose each town records its rainfall after a storm: 18 mm at A, 40 mm at B, 25 mm at C and 33 mm at D. Nearest-site interpolation estimates the rainfall at a point with no gauge by copying the reading of the nearest town, so every point in a cell gets that cell’s reading.
P at (8, 4) is in the cell of C, so its estimate is 25 mm. The point (3, 9) is in the cell of B: its squared distances are 53 to A, 5 to B, 65 to C and 53 to D. Its estimate is B’s reading, 40 mm.
Every point of C’s cell, in gold, gets C’s reading of 25 mm, P included.
A new town
Now add a fifth town, E at (6, 7). Its cell is every point nearer to E than to any of the older towns, and it is cut out of the cells that were there before.
Each edge of E’s cell lies on the perpendicular bisector of E and one neighbor. B at (2, 7) is level with E, so their bisector is the vertical line x = 4. The bisector of E and C is 5y − x = 16, and the bisector of E and D is x + y = 17. E’s cell has corners (4, 4), (11.5, 5.5), (5, 12) and (4, 12), with its top edge on the border of the map.
The corner (11.5, 5.5) is a new vertex: its squared distance is 32.5 to each of C, D and E. The corner (4, 4) was already a vertex of A, B and C, and E is from it too, the same as those three, so four cells meet at that point.
E’s cell, in gold, with edges against B, C and D and its top edge on the border of the map.
The old cells shrink
Adding E changes no distance between a point and an older town. A point leaves its old cell only when E is nearer to it than its old town was, so the old cells lose points and gain none. A cell can shrink or stay the same, and no cell can grow.
The point (5, 8) was in B’s cell: its squared distances are 52 to A, 10 to B, 40 to C and 34 to D. Its squared distance to E is , so it now belongs to E. B’s cell had corners (4.5, 12), (0, 12), (0, 4.8), (4, 4) and (7, 7); with E added it is (4, 12), (0, 12), (0, 4.8) and (4, 4), everything to the left of x = 4. The cells of C and D lose pieces too. A’s cell does not change, because no point of it is nearer to E than to A.
B’s cell, in gold, before E is added. It reaches the vertex (7, 7).
B’s cell after E is added: it now stops at the line x = 4.
Move the new tower
Drag the gold tower P below. It is a fifth site among four fixed towers, and its cell is cut from theirs. Each wall of its cell lies on the perpendicular bisector of P and one fixed tower.
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
At (3, 2.5), P’s cell has 4 walls, one against each fixed tower, and its nearest tower is D, 2.13 away.
The usual mistakes
Choosing the second-nearest town. A point belongs to the cell of the nearest town only, so every distance has to be compared.
Stopping at a town whose distance comes out as a round number. From (4, 6), A is exactly 5 away, but B is nearer: the squared distances are 25 to A and 5 to B.
Averaging the readings. The mean of 18, 40, 25 and 33 mm is 29 mm, but nearest-site interpolation copies the one reading of the nearest town.
Choosing between two towns for a point on an edge. The two distances are equal, so the map does not prefer either.
Ambulances and supermarkets
In the first application below, a dispatcher finds the nearest ambulance station to two callers, and one of them is on an edge. In the second, a supermarket closes, and the stores whose cells share an edge with its cell take over its customers.
Worked example: Sending the Nearest Ambulance: a Caller Inside One Station's Cell, and a Caller on an Edge
Question 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.
1.From (4, 6), the squared distances are: to A, 32 + 42 = 25; to B, 52 + 42 = 41; to C, 12 + 42 = 17.
The squared distances from (4, 6) are 25 to A, 41 to B and 17 to C. 2.(a) C is nearest, at √17 ≈ 4.12 km. A is exactly 5 km away, which is farther, because 17 < 25.
(a) C is nearest, at √17 ≈ 4.12 km; the caller is in C's cell. 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.
From (9, 7) the squared distances are 89, 25 and 25: B and C are equally near. 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.
The edge between B and C is y = 12x + 52, and (9, 7) lies 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.
(b) The caller is on the edge between the cells of B and C, 5 km from each.
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
Common mistakes
- 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.
Worked example: A Supermarket That Will Close: Which Stores Take Over Its Customers, and One Customer's New Nearest Store
Question 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?
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.
The bisectors of P with A and with B: x + y = 7 and 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.
The bisectors of P with C and with D: x + y = 15 and 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).
P's cell has corners (0, 7), (5.5, 1.5), (9.5, 5.5), (5, 10) and (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.
(a) The bisector with D lies outside the cell, so A, B and C take over P's customers and 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.
The customer at (2, 8) is in P's cell, 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.
(b) Once P closes, A is nearest at 7 km, which is 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
Common mistakes
- 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.