IB Maths AI SL Topic 3 — Voronoi Diagrams Paper 1 & 2 Largest empty circle ~7 min read

Toxic Waste Dump Problem

The “toxic waste dump” problem — despite its name — is the general task of finding the point on a Voronoi diagram that is as far as possible from any site. Same diagram, opposite question to the previous note. The answer is always at one of the vertices, and the technique is the largest empty circle: try each vertex as a centre, find the radius (= distance to its nearest site), and pick the biggest.

📘 What you need to know

Goal: locate the point that maximises the distance to its nearest site. Applies to toxic waste dumps, new shops avoiding competitors, picnic spots away from noisy groups, etc.
The optimum is always at a vertex of the Voronoi diagram (in IB AI SL exam questions). Don’t search elsewhere.
Largest empty circle (LEC): the biggest circle centred at a vertex that contains no sites. The radius equals the distance from the vertex to its nearest site.
Property of a Voronoi vertex: it is equidistant from three sites. So the radius can be found by computing the distance to just ONE of those three sites.
Method: compute the LEC radius at each vertex, then pick the vertex with the biggest radius. That’s the answer.
Scale factor: if 1 unit = k km, the final real-world distance = (LEC radius in units) × k.

The largest empty circle

At any Voronoi vertex you can draw a circle that just touches its three equidistant sites — that circle contains no sites inside (by construction). Across different vertices, this “largest empty circle” has different radii. The biggest one corresponds to the most isolated point on the diagram.

Two Voronoi vertices, each with its largest empty circle. The radius at V₂ (blue) is larger than at V₁ (red), so V₂ is the optimal toxic-waste location — the most-isolated point. The radius equals the distance to any one of the three sites on the circumference.

The toxic waste dump algorithm optimum location = vertex with the LARGEST empty circle

radius at vertex V = distance from V to any of its three equidistant sites

🧭 Recipe — find the optimum location

List every internal vertex of the Voronoi diagram. (Boundary points don’t qualify in IB AI SL.)
For each vertex, compute its largest-empty-circle radius: the distance to one of the three equidistant surrounding sites.
Compare the radii. The vertex with the biggest radius is the optimum location.
State the coordinates of that vertex as the answer.
Convert to real-world distance if a scale is given: multiply the biggest radius by the scale factor.

Only one distance per vertex: because a Voronoi vertex is equidistant from its three boundary sites, you only need to compute ONE distance per vertex — not three. Big time-saver.

Worked examples

WE 1

Pick the optimum from given radii

A Voronoi diagram has three internal vertices V₁, V₂, V₃. The radii of their largest empty circles are 4.2, 5.8 and 3.6 respectively. Which vertex is the optimal location for a noise-sensitive picnic area?

“Most-isolated point” = vertex with biggest empty-circle radius r(V1) = 4.2 r(V2) = 5.8 ← largest r(V3) = 3.6 optimum: V2 (radius 5.8) “largest radius” = “furthest from any site”. Once radii are listed, the answer is just picking the maximum. No further calculation needed.

WE 2

Radius at a single vertex

A Voronoi vertex V(5, 6) is equidistant from its three surrounding sites. One of those sites is at A(2, 2). Find the radius of the largest empty circle centred at V.

V is a Voronoi vertex → equidistant from all 3 surrounding sites → ANY of the three distances works (they’re all equal) Compute VA VA = √((5−2)² + (6−2)²) = √(9 + 16) = √25 = 5 radius = 5 units “equidistant from 3 surrounding sites” is the DEFINITION of a Voronoi vertex. Computing one of the three is enough — saves doing all three.

WE 3

Compare radii at two vertices

A Voronoi diagram has two internal vertices: X(2, 3) and Y(8, 5). One of the sites adjacent to X is at A(5, 7); one adjacent to Y is at B(4, 12). Determine which vertex is the optimum location for a toxic waste site.

Radius at X XA = √((2−5)² + (3−7)²) = √(9+16) = √25 = 5 Radius at Y YB = √((8−4)² + (5−12)²) = √(16+49) = √65 ≈ 8.06 Compare √65 > 5 → Y is the optimum Y(8, 5) is the optimal location, radius √65 ≈ 8.06 units two vertices, two distances, pick the bigger. The exact-form √65 is often acceptable; convert to decimal only if asked for “to 3 sf”.

WE 4

Three vertices — with scale conversion

A Voronoi diagram has three internal vertices: V₁(2, 5), V₂(8, 3), V₃(7, 7). One of the adjacent sites to each vertex is: for V₁, S₁(5, 1); for V₂, S₂(4, 6); for V₃, S₃(1, −1). 1 unit on the diagram represents 50 km. Find the optimal toxic-waste-dump location and the distance from this point to its nearest community in km.

Radii at each vertex r(V1) = √((2−5)² + (5−1)²) = √(9+16) = 5 r(V2) = √((8−4)² + (3−6)²) = √(16+9) = 5 r(V3) = √((7−1)² + (7−(−1))²) = √(36+64) = √100 = 10 Compare 10 > 5 → V3 is optimum Convert with scale real distance = 10 × 50 = 500 km site at V3(7, 7), distance = 500 km V1 and V2 are TIED at radius 5, but neither wins because V3 beats both. Ties between losers don’t matter. (6, 8, 10) is the (3, 4, 5) triple ×2.

WE 5

Symbolic radii + scale conversion

A Voronoi diagram has two internal vertices. Vertex X is equidistant from its three surrounding sites at distance √20 units. Vertex Y is equidistant from its three surrounding sites at distance √45 units. The scale is 1 unit = 100 m. Determine the optimal location for a noise-sensitive activity and state its distance to the nearest site, in metres (to 3 sf).

Simplify each surd √20 = 2√5 ≈ 4.47 √45 = 3√5 ≈ 6.71 Compare: 3√5 > 2√5 → Y wins Convert to metres using the scale distance = 3√5 × 100 = 300√5 ≈ 670.82 m Y is optimum, distance ≈ 671 m (3 sf) comparing surds: factor out common parts (here both are √5 × integer). The bigger integer wins. Keep exact form 300√5 through the multiplication; round at the end.

WE 6

From three sites — find vertex, then radius, then real distance

A logging company has three camps at L₁(0, 0), L₂(12, 0), L₃(0, 16). They want to place a wildlife sanctuary at the point on the Voronoi diagram that is furthest from every camp. 1 unit on the diagram represents 5 km. (a) Find the coordinates of the sanctuary. (b) Find the distance from the sanctuary to its nearest camp in km.

(a) Optimum is the unique internal vertex (circumcentre of the camps) ⊥L1L2: L1L2 horizontal, midpoint (6, 0) → x = 6 ⊥L1L3: L1L3 vertical, midpoint (0, 8) → y = 8 Intersection V = (6, 8) (b) Radius = distance from V to any camp VL1 = √(36 + 64) = √100 = 10 units VL2 = √(36 + 64) = 10 ✓ VL3 = √(36 + 64) = 10 ✓ Real distance using scale distance = 10 × 5 = 50 km (a) sanctuary at (6, 8) · (b) 50 km camps form a right triangle (right angle at L1). For a right triangle, the circumcentre (= Voronoi vertex) is the MIDPOINT of the hypotenuse, and the circumradius = half the hypotenuse. Useful shortcut. Here hypotenuse L2L3 = √(144+256) = 20; midpoint (6,8); half = 10. ✓

💡 Top tips

Only ONE distance per vertex: a Voronoi vertex is equidistant from its three surrounding sites, so computing one suffices. Saves time and reduces error.
Optimum is always a vertex (in IB AI SL). Don’t waste time checking interior points or boundary points.
Pythagorean triples: (3,4,5), (5,12,13), (6,8,10), (8,15,17). Common in well-designed exam questions.
Right-triangle shortcut: if three sites form a right-angled triangle, the Voronoi vertex is the MIDPOINT of the hypotenuse, and its radius is HALF the hypotenuse. Spot this whenever you can.
Keep exact form during comparison: √20 vs √45 is just 2√5 vs 3√5. Decimals only at the end.

⚠ Common mistakes

Picking the vertex with the SMALLEST radius: that’s the closest one to its nearest site. Optimum is the LARGEST radius (furthest from sites).
Computing distance to the wrong site: a Voronoi vertex has three equidistant sites — ignore any other sites in the diagram (they’re necessarily further).
Forgetting the scale conversion: if 1 unit = k km/m, multiply the final radius by k.
Mixing up “optimum location” with “nearest site”: the optimum is a VERTEX of the diagram, not a site. Don’t write “site C is the optimum”.
Square-root mistakes: r² = 65 means r = √65, not 65. Square-root the final value.

That completes the Voronoi Diagrams chapter. Across three notes you’ve learned to: draw a diagram via perpendicular bisectors, interpret a diagram for cell membership and nearest-site predictions, and find the optimum “furthest from any site” point using the largest empty circle. AI SL examines all three, often in the same problem. Combined with the rest of Topic 3 (coordinate geometry, trigonometry, 3D), you now have every tool the syllabus asks for in the geometry/trigonometry strand.

Need help with AI SL Voronoi Diagrams?

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

Book Free Session →

IB Demystified is a trusted online learning platform led by certified IB examiners and educators.