Voronoi Applications (AI HL)

In a Voronoi diagram, every point in a cell is closer to that cell's site than to any other site. To decide which site serves a point, calculate its distance to each candidate site and choose the smallest. The same idea gives nearest neighbour interpolation, the effect of adding a new site, and the toxic waste dump problem, which looks for the point as far as possible from its nearest site. It's part of the broader Voronoi Diagrams topic.

19 questions on this sub-topic.

Syllabus

CodeSyllabus content
SL3.6Voronoi diagrams: sites, vertices, edges and cells. Addition of a site to an existing Voronoi diagram. Nearest neighbour interpolation. Applications of the "toxic waste dump" problem. Site coordinates are given in exams for calculating the perpendicular bisector equations - you are not required to physically construct the diagram. Questions may ask for the equation of a boundary, the site closest to a given point, or the area of a region.

Official IB source: Mathematics: applications and interpretation subject brief (PDF, ibo.org).

Skills practised on this page:

Key formula

The distance formula does the actual comparing; the vertex rule locates the best or worst point in a region.

Distance to a site

d=(x2−x1)2+(y2−y1)2d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}

In the formula booklet under prior learning. Compute this to every candidate site and compare - the smallest value gives the site whose cell contains the point.

Finding a Voronoi vertex

Solve two bisector equations simultaneously - the intersection is equidistant from all three sites involved, and is where exactly three edges meet in exam questions. It's the point a toxic waste dump problem is looking for.

Not in the formula booklet - simultaneous equations

Need the full syllabus wording and formula reference table? See Voronoi Diagrams.

Key terms

What is a site?

A site is one of the given points around which a cell is built, such as a hospital, a school or a weather station. Every point in a cell has that cell's site as its nearest site.

e.g. Fire stations at F1(2,1)F_1(2,1), F2(9,2)F_2(9,2) and F3(5,7)F_3(5,7) are three sites.

What is nearest neighbour interpolation?

It estimates an unknown value at a point using the known value at the nearest site. The nearest site is found by comparing distances.

e.g. Sites A(0,0)A(0,0) and B(10,0)B(10,0) have recorded values 1212 and 2020. The point P(4,3)P(4,3) is 55 from AA and 45≈6.7\sqrt{45}\approx6.7 from BB, so the estimate at PP is 1212.

What is a Voronoi vertex?

A Voronoi vertex is a point where three cell edges meet, so it is equidistant from the three sites involved. It is found by solving two perpendicular bisector equations simultaneously.

e.g. Sites (0,0)(0,0), (4,0)(4,0) and (0,4)(0,4) have a vertex at (2,2)(2,2), which is 8\sqrt8 from each of the three sites.

How does adding a new site change a diagram?

The new site gets its own cell, bounded by perpendicular bisectors between it and its neighbours. Existing cells can only shrink, never grow, because some of their points are now nearer the new site.

e.g. If a site is added at (6,0)(6,0) to a diagram with a site at (0,0)(0,0), the edge between these two sites lies on the line x=3x=3.

Worked examples

1
Easy
GDC
[4 marks]

Sites are at A(0,0)A(0,0) and B(8,0).B(8,0). Which site is the point P(3,4)P(3,4) closer to?

(a)(i) Find the distance from PP to AA.

(a)(ii) State which site PP is closer to.

Worked solution

(a)(i) PA=9+16PA = \sqrt{9 + 16} M1
PA=5.PA = 5. A1

(a)(ii) PB=41≈6.40.PB = \sqrt{41} \approx 6.40. A1
Since PA<PBPA < PB, PP is in site A's cell. A1On the GDC. Find the distance from P to A The calculator shows about 5. The calculator steps below are for (a)(i).

TI-84 Plus CE: 2nd mode then type √(3^2+4^2) enterCasio fx-CG50: MENU Run-Matrix then type √(3^2+4^2) EXECasio fx-CG100: HOME Calculate then type √(3^2+4^2) EXETI-Nspire CX: home Calculator then type √(3^2+4^2) enterFull GDC guide: Enter a calculation on the home screen Topic page

M1 PAPA A1 Correct answer of 55 A1 PBPB A1 Cell A
2
Medium
GDC
[5 marks]

Hospitals are at H1(1,2)H_1(1, 2), H2(7,3)H_2(7, 3) and H3(4,8).H_3(4, 8). An accident occurs at P(5,4).P(5, 4). Determine the nearest hospital.

Worked solution

Use the distance formula (x2−x1)2+(y2−y1)2\sqrt{(x_2-x_1)^2+(y_2-y_1)^2}: M1
PH1=20≈4.47,PH_1 = \sqrt{20} \approx 4.47, A1
PH2=5≈2.24,PH_2 = \sqrt5 \approx 2.24, A1
PH3=17≈4.12.PH_3 = \sqrt{17} \approx 4.12. A1
Smallest is PH2PH_2, so H2H_2 is nearest. A1On the GDC. Evaluate each distance and compare.

TI-84 Plus CE: home screen.
Casio fx-CG50: Run-Matrix.
Casio fx-CG100: HOME → Calculate.
TI-Nspire CX: Calculator.

M1 Distance formula A1 PH1PH_1 A1 PH2PH_2 A1 PH3PH_3 A1 H2H_2
3
Hard
GDC
[5 marks]

A Voronoi vertex is at (3,3)(3,3) and its nearest site is A(0,0).A(0,0).

-2-1123456789-2-1123456780AVxy

Find the radius of the largest empty circle centred there.

Worked solution

Radius == distance to the nearest site =9+9= \sqrt{9 + 9} M1
giving 18\sqrt{18} A1
giving 323\sqrt2 M1
A1
≈4.24.\approx 4.24. A1On the GDC. Evaluate 18\sqrt{18} directly.

TI-84 Plus CE: home screen.
Casio fx-CG50: Run-Matrix.
Casio fx-CG100: HOME → Calculate.
TI-Nspire CX: Calculator.

M1 Radius = distance to nearest A1 18\sqrt{18} M1 Simplifying 18\sqrt{18} to 323\sqrt2 A1 323\sqrt2 A1 Correct answer of ≈4.24\approx4.24

Common mistakes

  • Mistaking a Voronoi vertex for a site. The point a toxic waste dump question asks for is a vertex - equidistant from three or more sites where cell boundaries meet - not one of the fixed points you were originally given.
  • Judging the nearest site from the picture instead of calculating. Diagrams in these questions aren't always drawn to scale - substitute the coordinates into the distance formula for every candidate site rather than guessing which one looks closest.
  • Reporting the vertex itself instead of its distance to the sites. A toxic waste dump answer usually wants a radius or distance value, not just the coordinates of the vertex - re-read what the question is actually asking for before you stop.

Quick questions

How do I decide which site serves a given point?

Calculate the distance from the point to each candidate site using the distance formula, then compare the values - the smallest distance identifies the site whose Voronoi cell contains that point.

What is the toxic waste dump problem?

It asks you to find the point as far as possible from every site within a bounded region - the answer is always a Voronoi vertex, and the radius of the largest empty circle centred there gives the maximum distance achieved.

Do I need to draw the diagram to find the nearest site?

No. Calculate the distance from the point to each site and compare them. For example, P(2,1)P(2,1) is 5\sqrt5 from A(0,0)A(0,0) and 55 from B(5,5)B(5,5), so AA is nearer.

What does it mean if a point is the same distance from two sites?

The point lies on the edge between the two cells, on the perpendicular bisector of the two sites. For example, (3,5)(3,5) is 34\sqrt{34} from both (0,0)(0,0) and (6,0)(6,0), and it lies on the line x=3x=3.

How do I find the distance asked for in a toxic waste dump problem?

Once the Voronoi vertex is found, calculate its distance to any one of the three sites meeting there, since all three distances are equal. For example, the vertex (3,2)(3,2) is 13≈3.61\sqrt{13}\approx3.61 from the sites (0,0)(0,0), (6,0)(6,0) and (0,4)(0,4).

Ready to practise properly?

19 Voronoi-application questions, marked instantly like the real exam.