The Toxic Waste Dump Problem

As far as possible from every town

Four towns stand in a square region from 0 to 12 on both axes: A at (1, 2), B at (2, 7), C at (7, 2) and D at (10, 11). A waste dump has to go somewhere in the region, as far as possible from every town.

Being far from every town means being far from the nearest one. So each point of the region has one number that matters, its distance to its nearest town, and the dump goes where that number is largest.

The four towns and their Voronoi cells, in the region from 0 to 12.

Never inside a cell

Inside a cell there is one nearest town. Step straight away from it and the distance to it grows, while every other town is still farther, for a short enough step. So the point can always be improved, and no point inside a cell is the best.

The point (9, 3) is in C’s cell, $\sqrt{5}\approx 2.24$√5 ≈ 2.24 from C. Moving on in the same direction to (11, 4) gives squared distances 104 to A, 90 to B, 20 to C and 50 to D: C is still nearest, now $\sqrt{20}\approx 4.47$√20 ≈ 4.47 away.

P at (9, 3) is 2.24 from C, its nearest town.

Farther along the same direction, at (11, 4), P is 4.47 from C, and C is still its nearest town.

Along an edge

On an edge between two cells, the two towns are equally near. The edge between C and D lies on their perpendicular bisector, and along it the distance to both towns is least at the midpoint of CD, (8.5, 6.5), which is $\sqrt{22.5}\approx 4.74$√22.5 ≈ 4.74 from each. Moving along the edge away from that midpoint, the distance grows.

This edge runs from the vertex (7, 7), 5 from C and D, to the border at $\left(12,\frac{16}{3}\right)$(12, 16/3), about 6.01 from C and D. The best point of an edge is at one of its ends. In the same way, along a straight stretch of the border inside one cell, the distance to that cell’s town is least at the point of the stretch closest to the town and grows on either side of it, so the best point is at an end of the stretch: a corner, or a point where an edge meets the border.

So only three kinds of point can be the answer: the Voronoi vertices, the corners of the region, and the points where an edge meets the border.

M, the midpoint of CD, is on the edge between their cells, 4.74 from each: the nearest the edge comes to them.

The vertices and their empty circles

At a Voronoi vertex three cells meet, so three towns are equally near. The vertex (4, 4) is $\sqrt{13}\approx 3.61$√13 ≈ 3.61 from A, B and C. A circle centered at (4, 4) through those three towns holds no town inside it: D is $\sqrt{85}\approx 9.22$√85 ≈ 9.22 away, outside. This is an empty circle, and its radius is the distance from its center to the nearest town.

The other vertex, (7, 7), is exactly 5 from B, C and D, and A is $\sqrt{61}\approx 7.81$√61 ≈ 7.81 away. Its empty circle has radius 5, bigger than the radius at (4, 4), so (7, 7) is the better vertex.

The empty circle at (4, 4) passes through A, B and C, radius 3.61, and holds no town.

The empty circle at (7, 7) passes through B, C and D, radius 5.

The border

The largest empty circle at a vertex has radius 5, but the border of the region has candidates too. Each corner is measured to its nearest town: (0, 0) and (12, 12) are $\sqrt{5}\approx 2.24$√5 ≈ 2.24 from A and from D, and (12, 0) and (0, 12) are $\sqrt{29}\approx 5.39$√29 ≈ 5.39 from C and from B. The corners (12, 0) and (0, 12) already beat both vertices.

Four edges meet the border. The edge between A and B meets it at (0, 4.8), $\sqrt{8.84}\approx 2.97$√8.84 ≈ 2.97 from A and B. The edge between A and C meets it at (4, 0), $\sqrt{13}\approx 3.61$√13 ≈ 3.61 from A and C. The edge between B and D meets it at (4.5, 12), $\sqrt{31.25}\approx 5.59$√31.25 ≈ 5.59 from B and D.

The edge between C and D meets the east side at $\left(12,\frac{16}{3}\right)$(12, 16/3). Its squared distance to C is $5^2+{\left(\frac{16}{3}-2\right)}^2$5² + (16/3 − 2)², which is $25+\frac{100}{9}=\frac{325}{9}$25 + 100/9 = 325/9, so it is $\sqrt{\frac{325}{9}}\approx 6.01$√(325/9) ≈ 6.01 from C, and the same from D.

The corner K at (0, 12) is 5.39 from B, its nearest town, farther than either vertex.

The best site

Of all ten candidates, the largest distance to the nearest town is about 6.01, at $\left(12,\frac{16}{3}\right)$(12, 16/3), where the edge between C and D meets the east side of the region. That is where the dump goes. The circle centered there with radius 6.01 passes through C and D and holds no town inside it.

Testing the vertices alone gives (7, 7) and 5. Testing the vertices and the corners gives 5.39. Only the full list, with the points where the edges meet the border, finds 6.01.

W at $\left(12,\frac{16}{3}\right)$(12, 16/3), where the edge between C and D meets the border, is 6.01 from C and 6.01 from D: the best site for the dump.

The usual mistakes

Measuring to the farthest town. From (4, 4), D is 9.22 away, but the dump is limited by its nearest town, 3.61 away.

Giving the diameter of the empty circle. The distance to the nearest town is the radius.

Stopping at the vertices. Here a corner and a point on the border are both farther from their nearest towns than either vertex.

Measuring a corner to the wrong town. (12, 0) is $\sqrt{125}\approx 11.18$√125 ≈ 11.18 from A and from D, but its nearest town is C, at $\sqrt{29}\approx 5.39$√29 ≈ 5.39.

Landfills and fireworks

In the first application below, a landfill site among three towns is found at a corner of the county, after the vertex and the edges’ ends on the border are compared. In the second, a fireworks depot is placed among four villages, and the search is run again when a new village is planned.