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
| Code | Syllabus content |
|---|---|
| SL3.6 | Voronoi 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:
- Add a new site to an existing Voronoi diagram and update the affected cells.
- Use a Voronoi diagram to determine the nearest neighbour to a given point.
- Solve a "toxic waste dump" style optimum-placement problem using a Voronoi diagram.
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
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 equationsNeed 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 , and 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 and have recorded values and . The point is from and from , so the estimate at is .
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 , and have a vertex at , which is 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 to a diagram with a site at , the edge between these two sites lies on the line .
Worked examples
Sites are at and Which site is the point closer to?
(a)(i) Find the distance from to .
(a)(ii) State which site is closer to.
Worked solution
(a)(i) M1
A1
(a)(ii) A1
Since , 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).
Hospitals are at , and An accident occurs at Determine the nearest hospital.
Worked solution
Use the distance formula : M1
A1
A1
A1
Smallest is , so is nearest. A1On the GDC. Evaluate each distance and compare.
Casio fx-CG50: Run-Matrix.
Casio fx-CG100: HOME → Calculate.
TI-Nspire CX: Calculator.
A Voronoi vertex is at and its nearest site is
Find the radius of the largest empty circle centred there.
Worked solution
Radius distance to the nearest site M1
giving A1
giving M1
A1
A1On the GDC. Evaluate directly.
Casio fx-CG50: Run-Matrix.
Casio fx-CG100: HOME → Calculate.
TI-Nspire CX: Calculator.
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, is from and from , so 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, is from both and , and it lies on the line .
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 is from the sites , and .
Ready to practise properly?
19 Voronoi-application questions, marked instantly like the real exam.