3.4A

The Toxic Waste Dump Problem

  • The Problem: A regional government wants to build a toxic waste disposal plant (or nuclear repository or noisy airport) such that it is located as far away as possible from any existing residential town.
  • Mathematical Formulation: Given a set of sites $S = \{S_1, S_2, \dots, S_n\}$, find a point $P(x, y)$ within a specified bounded feasible region that maximizes: $$\min_{i} d(P, S_i)$$
  • This is equivalent to finding the center of the Largest Empty Circle (LEC) whose interior contains zero sites and with radius equal to the distance to the nearest site. Its centre is constrained to the allowed region; its circumference need not pass through three sites.
3.4B

The Largest Empty Circle Theorem

  • Core Theorem: The center of the largest empty circle must be located either at:
    1. A Voronoi vertex inside a bounded polygonal region.
    2. An intersection of a Voronoi edge with the boundary.
    3. A vertex of the polygonal boundary, such as a corner of a rectangular territory.
  • Why? A Voronoi vertex $V$ is equidistant from at least three nearest sites $A, B, C$. The circle centered at $V$ with radius $r = d(V, A) = d(V, B) = d(V, C)$ is the circumcircle of triangle $ABC$, and by definition of a Voronoi vertex, its interior contains no other sites!

Solved Example: Identifying the Optimal Site

Four villages are located at $A(0, 4)$, $B(6, 4)$, $C(3, 0)$, and $D(3, 8)$. The Voronoi diagram has two vertices: $V_1(3, 2.875)$ and $V_2(3, 5.125)$. Find which vertex provides the greater clearance distance for a waste repository.

Step 1: Calculate radius for $V_1(3, 2.875)$: Distance to site $C(3, 0)$: $$r_1 = \sqrt{(3 - 3)^2 + (2.875 - 0)^2} = 2.875\text{ km}$$
Step 2: Calculate radius for $V_2(3, 5.125)$: Distance to site $D(3, 8)$: $$r_2 = \sqrt{(3 - 3)^2 + (5.125 - 8)^2} = \sqrt{(-2.875)^2} = 2.875\text{ km}$$
Step 3: Symmetry evaluation: Both vertices offer identical clearance of $2.875\text{ km}$. Either vertex is equally good among these two candidates. A global optimum requires comparing all permitted boundary candidates too.

Final Answer: Clearance radius = $2.88\text{ km}$ at $V_1$ or $V_2$

Compare every feasible candidate

  • Objective: $r(P)=\min_i d(P,S_i)$. Maximise this nearest-site distance, not the largest distance or the sum of distances.
  • For distinct sites and a closed bounded polygonal feasible region, list interior Voronoi vertices, retained Voronoi-edge intersections with the polygon boundary, and polygon corners. Discard points outside the allowed region.
  • At every candidate compute distances to all sites and retain the smallest. A circumcentre from three sites is invalid as an empty-circle candidate if a fourth site lies closer.
  • Within one Voronoi cell, the objective is distance to its generating site. On the clipped polygon, this convex distance reaches a maximum at a polygon vertex; those vertices are precisely the candidate types above.
  • The circle’s centre must be feasible. The circle itself need not lie wholly inside the territory unless the question adds that constraint; requiring containment creates a different optimisation problem.
  • Non-polygonal boundaries, exclusion zones and restricted access require the candidate argument to be reconsidered.

Complete bounded example and interpretation

  • Territory: $0\le x\le6$, $0\le y\le4$, sites A(1,2), B(5,2). The Voronoi edge is $x=3$.
  • Candidates: (0,0), (0,4), (6,0), (6,4) have clearance $\sqrt5$. Edge-boundary intersections (3,0), (3,4) have clearance $\sqrt8$. There are no interior vertices.
  • Conclusion: (3,0) and (3,4) both maximise clearance at $2\sqrt2\approx2.83$ units. The tied optimum demonstrates why boundaries cannot be omitted.
  • Convert map distance to real distance before interpreting safety. A clearance is a model output, not proof of environmental safety.
  • Population, prevailing wind, groundwater, road access, flood risk, construction cost and legal restrictions can change the decision. Identify which assumptions the simple point-distance model omits.
A (1,2)B (5,2)x = 306
In the territory 0 ≤ x ≤ 6, 0 ≤ y ≤ 4, the shared boundary is x = 3.

10 Progressive Practice Exercises

Attempt each problem before opening its solution. Keep exact values until the final answer.

Exercise 1 (Paper 2 — 5 Marks): Three hospitals are located at $A(1, 2)$, $B(5, 2)$, and $C(3, 6)$.
  1. Show that the Voronoi vertex formed by these hospitals is $V(3, 3.5)$.
  2. Calculate the clearance radius from $V$ to any of the hospitals, correct to 3 s.f.
(a) Segment $AB$ is horizontal ($y=2$), midpoint is $(3, 2)$. Perpendicular bisector is $x = 3$. [M1][A1]
Midpoint of $AC = \left(\frac{1+3}{2}, \frac{2+6}{2}\right) = (2, 4)$.
$m_{AC} = \frac{6-2}{3-1} = \frac{4}{2} = 2 \implies m_{\perp} = -\frac{1}{2}$.
Bisector of $AC$: $y - 4 = -\frac{1}{2}(x - 2) \implies y = -\frac{1}{2}x + 5$. [M1]
Substitute $x = 3$: $y = -\frac{1}{2}(3) + 5 = -1.5 + 5 = 3.5 \implies V(3, 3.5)$. [A1]
(b) Distance from $V(3, 3.5)$ to $A(1, 2)$: $$r = \sqrt{(3-1)^2 + (3.5-2)^2} = \sqrt{2^2 + 1.5^2} = \sqrt{4 + 2.25} = \sqrt{6.25} = 2.50\text{ units}$$ [M1][A1]

Answer: (a) Verified, (b) $2.50\text{ units}$

Exercise 2 🟢 Core

A candidate has distances 7, 3 and 5 km to three towns. Find its clearance and compare with a candidate whose distances are 4, 4 and 8 km.

Clearances are min(7,3,5)=3 km and min(4,4,8)=4 km. The second is better despite its smaller maximum distance.
Exercise 3 🟢 Core

For A(1,2), B(5,2) in $[0,6]\times[0,4]$, list every candidate and find all optimal centres.

Corners give $\sqrt5$; (3,0) and (3,4), where $x=3$ meets the boundary, give $\sqrt8$. Both latter points are optimal. There are no interior Voronoi vertices.
Exercise 4 🟡 Standard

A single town lies at (1,1) in the square $[0,4]\times[0,4]$. Find the optimal centre.

Corner distances are $\sqrt2,\sqrt{10},\sqrt{10},\sqrt{18}$. The farthest point is (4,4), with clearance $3\sqrt2$. No Voronoi vertex is needed.
Exercise 5 🟡 Standard

Three sites lie 5 km from a proposed circumcentre, while a fourth lies 2 km from it. Is the radius-5 circle empty?

No. The fourth site is inside that circle. The actual clearance is 2 km; equal distances to three sites alone do not establish a Voronoi vertex.
Exercise 6 🟡 Standard

Candidates P and Q have nearest-site distances $\sqrt{20}$ and $\sqrt{18}$ map units. One unit is 2 km. Which is better, and what is its real clearance?

P is better because $\sqrt{20}>\sqrt{18}$. Its clearance is $2\sqrt{20}=4\sqrt5\approx8.94$ km. Compare unrounded values first.
Exercise 7 🟡 Standard

A vertex (3,5) offers 6 km clearance but the feasible rectangle is $[0,6]\times[0,4]$. A feasible corner offers 4 km. Can the vertex be selected?

No: its y-coordinate exceeds 4. Discard infeasible candidates, then compare the corner with all other feasible candidates; 4 km alone does not establish global optimality.
Exercise 8 🔴 Challenge

With finitely many towns, explain why maximising clearance over the entire plane has no finite solution.

Move sufficiently far from all towns: if every site lies within distance M of the origin, a point at distance R has clearance at least R−M. This grows without bound.
Exercise 9 🔴 Challenge

An allowed centre lies on the boundary of a territory, and its empty circle extends beyond it. Is this automatically invalid?

No, if only the centre is constrained. If the entire circle must be contained, distances to the boundary also limit the radius. State which model is being used.
Exercise 10 🔴 Challenge

Two sites A(1,2), B(5,2) lie in $[0,6]\times[0,4]$. A regulation requires clearance at least 3 units. Is any centre acceptable? Give a modelling limitation.

The maximum possible clearance is $\sqrt8\approx2.83<3$, so no centre meets the requirement. Straight-line distance alone does not account for wind, groundwater or population exposure.
Formulae

Largest Empty Circle Reference

Euclidean Distance / Radius:

$$r = \sqrt{(x_V - x_i)^2 + (y_V - y_i)^2}$$

For a bounded polygonal region, compare interior Voronoi vertices, Voronoi-edge/boundary intersections and boundary vertices. At each candidate use the minimum distance to all sites. Without a bounded feasible region, the distance can grow without limit.

Examiner Pitfalls

Common Exam Traps in Facility Siting

  • Forgetting to Check Boundaries: In questions with a defined bounded rectangular territory $[x_{\min}, x_{\max}] \times [y_{\min}, y_{\max}]$, the optimal site might be on a boundary corner if all vertices are constrained near the interior.
  • Testing Only One Vertex: If a Voronoi diagram has multiple vertices $V_1, V_2, V_3$, you must calculate the radius for each vertex and compare them explicitly before declaring the maximum.
Topic 3.4 Check

Exam Mini Test (5 Questions)

Score: 0 / 5

1. In the toxic waste dump problem, what geometric object's center gives the optimal site location?

2. If a Voronoi vertex $V$ is equidistant from sites $A, B,$ and $C$ at a distance of $4.5\text{ km}$, what is the radius of the empty circle centered at $V$?

3. Which distance is maximised in the clearance model?

4. Must a largest-empty-circle centre be an interior vertex?

5. Three sites are 5 km away; another is 2 km away. What is the clearance?