IB Maths AI HL Voronoi Diagrams Paper 1 & 2 Largest empty circle ~8 min read

Toxic Waste Dump Problem

The toxic waste dump problem asks: given a set of sites on a Voronoi diagram, where is the point furthest from any of them? In exam contexts, the answer is always a vertex of the diagram — the centre of the largest empty circle that fits inside without touching any site. The radius of that circle is the distance from the vertex to its nearest site, found via Pythagoras.

📘 What you need to know

The problem: find the point on the Voronoi diagram that maximises the distance to the nearest site — useful for placing things equally far from competitors, neighbours, or hazards.
The answer is always a vertex — in IB exam questions, the optimal point sits at a vertex of one of the Voronoi cells (the only candidates).
Largest empty circle: a circle centred at a vertex with no site inside, expanding until it just touches the nearest site — the closest site lies on the circumference.
Radius = distance from the vertex to its nearest site, computed by Pythagoras: r = √((x_v−x_s)² + (y_v−y_s)²).
Choosing between vertices: when several vertices exist, compute the radius of each empty circle and pick the vertex with the largest one — that’s the optimal location.
Scale conversion: if 1 unit = k km (or m), the real-world distance is (radius in units) × k. Apply this only at the end.

Largest empty circle — the key idea

Imagine inflating a balloon centred at a vertex of the Voronoi diagram. It expands freely until it touches the nearest site — at that moment, the balloon is the largest empty circle at that vertex. The radius equals the distance from the vertex to its nearest site. The toxic waste dump should sit at whichever vertex has the largest balloon, because that vertex is the furthest possible from any inhabited site.

The largest empty circle at V₂ (radius r₂) is bigger than the one at V₁ (radius r₁). The optimal toxic-waste site is therefore V₂ — the vertex with the larger empty circle — with distance r₂ to the nearest existing site.

Largest empty circle at a vertex V r = √((x_v − x_s)² + (y_v − y_s)²) where S(x_s, y_s) is V’s nearest site. Optimal vertex = arg max of r.

Solving the problem in practice

Most exam questions give you the vertex coordinates and the diagram. Your job is to compute the radius of the empty circle at each candidate vertex (i.e. distance from that vertex to its nearest site), pick the largest, and report the result — converted to real-world units if a scale is given. The “nearest site” at a vertex is any of the three sites equidistant from it; pick any of them for the distance calculation. If you need to compute the vertex itself, solve two of the edge equations simultaneously.

Beyond toxic waste: this same method finds the best location for anything that should be as far as possible from existing competitors — new supermarket, new tree, quiet picnic spot, even sensor placement to maximise coverage gaps.

🧭 Recipe — toxic waste dump problem

Locate the candidate vertices — either given directly or by solving two perpendicular bisector equations simultaneously.
Identify a nearest site at each vertex (any of the three equidistant sites works).
Compute the radius using Pythagoras: distance from the vertex to its nearest site.
Compare radii across vertices — pick the vertex with the largest empty circle.
Apply the scale if given (1 unit = k km, etc.) to convert to real-world distance.

Worked examples

WE 1

Radius of the largest empty circle at a vertex

On a Voronoi diagram, the vertex V is at (3, 4). One of the three sites equidistant from V is P(0, 0). Find the radius of the largest empty circle that can be centred at V.

distance from V to its nearest site r² = (3−0)² + (4−0)² = 9 + 16 = 25 r = √25 = 5 r = 5 units 3-4-5 triple — the three equidistant sites all sit on a circle of radius 5 around V.

WE 2

Compare two candidate vertices

A Voronoi diagram has two candidate vertices for a toxic waste dump: X(1, 2), whose nearest site is P(4, 6); and Y(0, 0), whose nearest site is Q(8, 6). Determine which vertex should be chosen, and state the distance from that vertex to its nearest site.

radius of empty circle at X XP² = (4−1)² + (6−2)² = 9 + 16 = 25 r_X = 5 radius of empty circle at Y YQ² = (8−0)² + (6−0)² = 64 + 36 = 100 r_Y = 10 larger radius → pick Y choose Y; distance = 10 units two clean triples (3-4-5 and 6-8-10) make the comparison immediate.

WE 3

Find the vertex from two edge equations

On a Voronoi diagram, two edges that meet at vertex V have equations 3x − y = 5 and x + y = 7. The site nearest to V is S(0, 0). Find the coordinates of V and the radius of the largest empty circle centred at V.

solve simultaneously for V 3x − y = 5 x + y = 7 add the two equations 4x = 12 → x = 3 y = 7 − 3 = 4 → V = (3, 4) radius = distance from V to S r = √(9 + 16) = 5 V = (3, 4); r = 5 units solving two edge equations gives a vertex; the third edge will pass through it automatically.

WE 4

Largest empty circle with a scale

A Voronoi diagram for a national park has vertex V at (10, 4), with three equidistant sites including ranger station R(7, 0). The diagram uses a scale of 1 unit = 1.5 km. Find the radius of the largest empty circle at V, in kilometres.

radius in diagram units VR² = (10−7)² + (4−0)² = 9 + 16 = 25 r = 5 units convert with scale real radius = 5 × 1.5 km r = 7.5 km scale applied once, at the end — never multiply coordinates first.

WE 5

Two vertices — full comparison with metric scale

Two candidate locations for a new wind turbine are at vertices P(3, 2) and Q(5, 7) of a Voronoi diagram showing existing turbines. The nearest existing turbine to P is at A(0, 6), and the nearest to Q is at B(13, 13). The diagram uses a scale of 1 unit = 40 m. Determine which vertex should be chosen to maximise the distance to the nearest existing turbine, and state this distance in metres.

radius at P PA² = (3−0)² + (2−6)² = 9 + 16 = 25 r_P = 5 radius at Q QB² = (5−13)² + (7−13)² = 64 + 36 = 100 r_Q = 10 larger → Q wins; apply scale real distance = 10 × 40 m choose Q; distance = 400 m both calculations use 3-4-5 and 6-8-10 triples; the scale is applied to the winning value only.

WE 6

Full problem — find vertex, then compare

A Voronoi diagram has two candidate vertices. Vertex X lies at the intersection of x + y = 8 and 2x − y = 4. Vertex Y is at (4, 9). The site nearest to X is S₁(0, 0), and the site nearest to Y is S₂(3, 6). Determine which vertex would be the better toxic waste site and find the exact distance from that vertex to its nearest site.

find X from the two edge equations add: 3x = 12 → x = 4 y = 8 − 4 = 4 → X = (4, 4) radius at X (to S₁) r_X² = 16 + 16 = 32 r_X = √32 = 4√2 ≈ 5.66 radius at Y (to S₂) r_Y² = (4−3)² + (9−6)² = 1 + 9 = 10 r_Y = √10 ≈ 3.16 larger → X wins choose X; r = 4√2 units compare squared radii (32 vs 10) for the cleanest comparison.

💡 Top tips

The answer is always a vertex — never bother checking interior points or generic edge points in exam problems.
Compare squared radii — saves taking square roots when you only need to know which is bigger.
“Nearest site” is any of three at a vertex (the vertex is equidistant from three sites by definition) — pick whichever gives the cleanest distance calculation.
Solve two edge equations simultaneously to find a vertex, then use the radius formula.
Apply scale only at the end, after picking the winning vertex and computing its radius in diagram units.

⚠ Common mistakes

Picking the smaller radius — the optimal location is the vertex with the largest empty circle, because that’s the furthest from any existing site.
Forgetting the scale — reporting “5 units” instead of “5 × scale factor” in km or m.
Computing the wrong distance — the radius is V to nearest site, not V to some other site or to the centroid.
Solving only one edge equation for a vertex — you need two to fix the point’s coordinates.
Treating the centre of the diagram as the answer — the centre of a Voronoi diagram is usually not the furthest point from all sites; only vertices are.

Chapter complete — you now have all three Voronoi Diagrams sub-topics: Drawing (perpendicular bisectors, missing sites, edge equations), Interpreting (nearest site, shortest distance, nearest-neighbour interpolation), and the Toxic Waste Dump Problem (largest empty circle at a vertex). Together they cover every Paper 1 & 2 Voronoi question on the AI HL syllabus.

Need help with Voronoi Diagrams?

Get 1-on-1 help from an IB examiner who knows exactly what Paper 1 & 2 are looking for.

Book Free Session →