IB Maths AI HL Voronoi Diagrams Paper 1 & 2 Nearest neighbour ~8 min read

Interpreting Voronoi Diagrams

Once a Voronoi diagram is drawn, you can use it to answer real-world questions: which site is closest to a given point, what’s the shortest distance to that site, and what data should be used to predict outcomes at a new location. The standard tool is the distance formula, combined with the cell structure of the diagram — a point’s nearest site is simply the site of the cell it lies in.

📘 What you need to know

The nearest site is the site of the cell the point lies in — this is the defining property of a Voronoi diagram.
Distance formula: between points (x₁, y₁) and (x₂, y₂), d = √((x₂−x₁)² + (y₂−y₁)²) — Pythagoras’ theorem in coordinate form.
Edge equidistance: a point on an edge is equidistant from the two sites in the neighbouring cells — there’s no unique “nearest” site.
Nearest-neighbour interpolation: to predict a value at a new location, use the data from the nearest site. The prediction at the new location equals the value at that site.
Scale conversion: diagrams often use “1 unit = k km” (or m). Compute the distance in units first, then multiply by the scale factor.
Pythagorean triples (3-4-5, 5-12-13, 7-24-25, 8-15-17, 9-12-15) often appear — recognise them to skip the square root step.

Reading a Voronoi diagram

The cell a point lies in immediately tells you its nearest site — that’s the defining property of a Voronoi diagram. The shortest distance to that nearest site is then a Pythagoras calculation between the two coordinates. If the question gives a scale (e.g. “1 unit = 10 km”), do the distance in diagram units first, then multiply at the end. If a point sits exactly on an edge, it’s equally close to two sites — there’s no unique nearest one.

New point N(6, 8) sits in cell A — so the nearest site is A. Distance N to A is 4 units along the horizontal (both have y = 8). For nearest-neighbour interpolation, use A’s data to predict at N.

Distance between two points d = √((x₂ − x₁)² + (y₂ − y₁)²) real distance = (diagram distance in units) × (scale factor)

Nearest-neighbour interpolation

If you have data measured at each site (temperatures, sales, customer counts, pollution levels), you can predict the value at any new location using nearest-neighbour interpolation: the prediction equals the value at the nearest site. It’s a simple model — it assumes everything inside a cell behaves like its site — but it’s the standard approach the IB expects on AI HL. To use it: find the cell containing the new point, look up the data for that site, and report it as the prediction.

Don’t overthink it: nearest-neighbour interpolation does not weight or average values across neighbouring cells. It uses one value — the value at the nearest site. Identifying that site is the whole problem.

🧭 Recipe — using a Voronoi diagram

Locate the point on the diagram, or compute distances to each site if it’s not visually clear.
Identify the cell it lies in — this gives the nearest site.
Apply the distance formula between the point and the nearest site for the shortest distance.
Convert with the scale if one is given: real distance = (diagram distance) × (scale factor).
For interpolation, report the data value at the nearest site as the prediction.

Worked examples

WE 1

Identify the nearest site of four

A Voronoi diagram has four sites: A(2, 8), B(9, 7), C(4, 1), and D(11, 2). A new café opens at the location N(6, 5). By computing distances, determine which site’s sales data should be used to predict sales at N.

distance² from N to each site NA² = (6−2)² + (5−8)² = 16 + 9 = 25 NB² = (6−9)² + (5−7)² = 9 + 4 = 13 NC² = (6−4)² + (5−1)² = 4 + 16 = 20 ND² = (6−11)² + (5−2)² = 25 + 9 = 34 smallest squared distance ⇒ nearest site min = NB² = 13 → NB = √13 ≈ 3.61 use site B’s data compare squared distances to avoid unnecessary square roots.

WE 2

Shortest distance with a scale

A Voronoi diagram represents farms across a county, with site T at (3, 5). A new measuring station Q is located at (8, 17) and lies in T’s cell. The diagram uses a scale of 1 unit = 5 km. Find the shortest distance from Q to its nearest farm, in km.

distance from Q to T in diagram units QT = √((8−3)² + (17−5)²) = √(25 + 144) = √169 = 13 units convert with scale (1 unit = 5 km) real distance = 13 × 5 distance = 65 km 5-12-13 Pythagorean triple — no calculator needed.

WE 3

Point on an edge — equidistance

Sites A(1, 4) and B(7, 4) lie on a Voronoi diagram. A new monitoring station M(4, 7) is built on the edge between cells A and B. (a) Verify that M is on this edge. (b) Find the distance from M to each of A and B. (c) State which is the nearest site.

(a) AB is horizontal ⇒ ⊥ bisector is vertical midpoint AB = (4, 4); edge: x = 4 M has x = 4 ⇒ M is on the edge ✓ (b) distances MA = √((4−1)² + (7−4)²) = √(9+9) = √18 = 3√2 MB = √((4−7)² + (7−4)²) = √(9+9) = √18 = 3√2 MA = MB = 3√2 ≈ 4.24 (c) on an edge: two sites equidistant neither is strictly nearest — A and B are tied

WE 4

Comparing distances

In a region modelled by a Voronoi diagram, a hospital is at H(0, 0) and a clinic is at C(12, 5). A community centre is planned at V(8, 6). By computing distances, determine which facility is closer to V, and state its distance.

distance from V to each facility VH = √(8² + 6²) = √(64+36) = √100 = 10 VC = √((8−12)² + (6−5)²) = √(16+1) = √17 ≈ 4.12 compare √17 < 10 ⇒ V closer to C closer to clinic C; distance = √17 ≈ 4.12 units 6-8-10 triple gives clean VH; the smaller distance is to the clinic.

WE 5

Nearest-neighbour interpolation — temperatures

Three weather stations lie at W₁(2, 3), W₂(8, 4), and W₃(5, 9), with last-recorded temperatures of 18°C, 22°C, and 15°C respectively. An outdoor concert is planned at the point V(4, 7). Using nearest-neighbour interpolation: (a) determine which station’s data to use; (b) state the predicted temperature at V.

(a) squared distances VW₁² = (4−2)² + (7−3)² = 4 + 16 = 20 VW₂² = (4−8)² + (7−4)² = 16 + 9 = 25 VW₃² = (4−5)² + (7−9)² = 1 + 4 = 5 smallest is VW₃² = 5 nearest: W₃ (distance √5 ≈ 2.24) (b) nearest-neighbour prediction predicted temperature at V = 15°C interpolation uses W₃’s value because V lies in W₃’s cell.

WE 6

Distance with metric-scale conversion

A Voronoi diagram represents 6 retail stores in a city. One store is at site S(4, 2). A proposed new outlet L(13, 14) is found to lie in S’s cell. The diagram uses a scale of 1 unit = 250 m. Find the shortest distance from L to its nearest store, in kilometres.

distance LS in diagram units LS = √((13−4)² + (14−2)²) = √(81 + 144) = √225 = 15 units convert to metres, then km real = 15 × 250 m = 3750 m distance = 3.75 km 9-12-15 = 3·(3-4-5) — another classic triple.

💡 Top tips

Compare squared distances when checking which site is nearest — saves taking unnecessary square roots.
Recognise Pythagorean triples: 3-4-5, 5-12-13, 7-24-25, 8-15-17, 9-12-15 — if the differences match, the answer is an integer.
Apply the scale at the end, after computing in diagram units — cleaner arithmetic.
Watch for “on an edge” — if the point is on a Voronoi edge, it’s equidistant from two sites; state that explicitly.
Read the question for what is being asked: nearest site (name only), shortest distance (number with units), or interpolation (the data value at the nearest site).

⚠ Common mistakes

Distance formula slips — squaring (y₂ − y₁)² without the parentheses, missing the square root, or forgetting to add the two squared terms.
Forgetting to apply the scale — the answer in diagram units is not the answer in km.
Applying the scale twice — converting in the middle of the calculation and then again at the end.
Picking the wrong nearest site when distances are close — recompute or compare squared distances.
Averaging or weighting values from multiple sites for nearest-neighbour interpolation — the method uses just one value, from the nearest site.

Next up — the Toxic Waste Dump Problem. Same diagram, different question: find the point that’s furthest from any site. The answer is always a vertex of the Voronoi diagram, and the size of its “largest empty circle” decides which vertex wins.

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 →