Voronoi Diagrams (AI HL)
A Voronoi diagram carves up a plane into regions - one per site - so that every point in a region is closer to its own site than to any other. This topic covers finding the perpendicular bisector between two sites, reading off which site "owns" a given point, adding a new site to an existing diagram, and the classic optimal-placement application known as the toxic waste dump problem.
What the syllabus says
Voronoi diagrams are SL content within the Geometry & Trigonometry unit, examinable at both SL and HL.
| 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. |
In every exam question, the final solution point sits at the intersection of exactly three edges - if your two bisectors meet somewhere else, check your working.
Key terms
Five words worth knowing cold before you touch the formulas below - each with a worked example showing exactly what it means.
What is a Voronoi diagram?
A Voronoi diagram divides a plane into regions around a set of fixed points (the sites), so that every point inside a region is nearer to that region's site than to any other. The boundaries between regions are made of straight edges.
e.g. with two sites \(A(0,0)\) and \(B(6,0)\), the boundary between them is the vertical line \(x=3\), equidistant from both.
What is a site?
A site is one of the fixed points the diagram is built around - a shop, a weather station, a town. Every other point in the plane belongs to the cell of whichever site is nearest to it.
e.g. the point \((1,0)\) is 1 unit from site \(A(0,0)\) but 5 units from site \(B(6,0)\), so it lies in \(A\)'s cell.
What is a Voronoi cell?
A Voronoi cell is the region of the plane containing every point closer to one particular site than to any other. Cells are bounded by straight edges, each edge being part of a perpendicular bisector between two neighbouring sites.
e.g. for sites \(A(0,0)\) and \(B(6,0)\), \(A\)'s cell is every point with \(x<3\).
What role does a perpendicular bisector play?
The perpendicular bisector between two sites is the line of points exactly equidistant from both - it forms the shared edge of their two Voronoi cells. You find it from the midpoint and the negative reciprocal of the gradient between the sites.
e.g. for \(A(0,0)\), \(B(6,0)\), the point \((3,4)\) on the bisector \(x=3\) is \(\sqrt{9+16}=5\) from both \(A\) and \(B\).
What is the toxic waste dump problem?
It's a standard application: find the point as far as possible from every site within a bounded region - useful for siting something you want maximally distant from existing points. The answer is always a Voronoi vertex, where three or more cells meet.
e.g. for shops at the corners of a \(10\times10\) square, the farthest interior point is the centre \((5,5)\), at distance \(\sqrt{25+25}=5\sqrt2\approx7.07\) from each corner.
Key formulas
Voronoi diagrams lean on coordinate geometry you already know - the table below flags what's assumed prior knowledge, and the cards after it apply each idea to the topic.
Formula reference
The distance formula is the one genuinely booklet-listed result here; everything else is coordinate geometry from earlier in the course.
| Formula | Used for | Booklet? |
|---|---|---|
| \(\left(\dfrac{x_1+x_2}{2}, \dfrac{y_1+y_2}{2}\right)\) | Midpoint of two sites - a point on their bisector | Not in booklet - prior knowledge |
| Perpendicular gradient \(=-\dfrac{1}{m}\) | Direction of the bisector line | Not in booklet - prior knowledge |
| \(d = \sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}\) | Distance from a point to a site | ✓ Yes - prior learning section |
Inside a cell vs on a boundary
Every point in the plane is either strictly closer to one site, or exactly balanced between two or more.
| Feature | Point inside a cell | Point on a boundary edge |
|---|---|---|
| Nearest site | Exactly one nearest site | Two (or three, at a vertex) equally near sites |
| Distance relation | Strictly closer to one site than any other | Equal distance to the sites either side of that edge |
| Typical question | Nearest-neighbour interpolation - assign that site's value | "Which store serves this point?" - the answer is more than one |
Perpendicular bisectors
Every question builds on the same three-step process: midpoint, perpendicular gradient, then the equation itself.
Finding the bisector equation
Find the midpoint of the two sites and the negative reciprocal of the gradient between them, then write the line through that midpoint with that gradient.
Not in the formula booklet - coordinate geometryFinding a Voronoi vertex
Solve two bisector equations simultaneously - the intersection is equidistant from all three sites involved, and is always where exactly three edges meet in exam questions.
Not in the formula booklet - simultaneous equationsAdding a new site
Find the bisector between the new site and each existing site whose cell it might intersect, then redraw the boundaries - points closer to the new site move into its cell.
Not in the formula booklet - construction ruleApplications
The syllabus names two specific real-world uses that come up repeatedly in exam questions.
Nearest-neighbour interpolation
Every point in a site's cell is estimated to share that site's measured value - e.g. rainfall recorded at a weather station applies to its whole Voronoi cell.
Not in the formula booklet - modelling assumptionToxic waste dump problem
To place something as far as possible from every site within a region, look for the Voronoi vertex with the greatest distance to its surrounding sites.
Not in the formula booklet - optimisation applicationWhich site serves a point?
Compute (or compare) the distance from the point to each candidate site - the smallest distance identifies the site whose cell it lies in.
Not in the formula booklet - direct comparisonWorked examples
Two full exam-style questions, marked exactly like the real thing. Try each one yourself before checking the worked solution.
Sites \(A(2, 0)\), \(B(0, 4)\), \(C(6, 4).\)
(a) Find the perpendicular bisector of \(AB.\)
(b) Find the perpendicular bisector of \(BC.\)
(c) Find the Voronoi vertex (their intersection).
Worked solution
(a) Midpoint \(AB = (1,2)\), perp gradient \(\tfrac12\): \(y\) M1
\(= \tfrac12 x + \tfrac32.\) A1
(b) \(BC\) horizontal, midpoint \((3,4)\): \(x\) M1
\(= 3.\) A1
(c) At \(x = 3\): \(y\) M1
\(= 3.\) Vertex \((3, 3).\) A1
A region is served by two stores \(A(0,0)\) and \(B(10,0)\), divided by the line \(x = 5.\) A new store \(C(5, 8)\) opens. A customer is at \(P(5, 1).\)
(a)(i) Find the distance from \(P\) to store \(A.\)
(a)(ii) Find the distance from \(P\) to store \(B.\)
(a)(iii) Find the distance from \(P\) to store \(C.\)
(b) State which store now serves \(P.\)
Worked solution
(a)(i) \(PA = \sqrt{26} \approx 5.10.\) M1
\(PA=\sqrt{26}\approx5.10.\) A1
(a)(ii) \(PB = \sqrt{26} \approx 5.10.\) A1
(a)(iii) \(PC = 7.\) A1
(b) \(P\) is equidistant from A, B and closer to them than C, so on the A–B boundary. M1
\(P\) is served by both \(A\) and \(B\), not \(C\). A1
Common mistakes
The four slip-ups that account for most of the marks lost on this topic - worth reading before you start practising, not just after you get one wrong.
- Confusing a Voronoi vertex with a site. A vertex is a point equidistant from three or more sites, where cell boundaries meet - it is not one of the original given points.
- Using the same gradient as the line joining two sites. A perpendicular bisector needs the negative reciprocal of that gradient, not the gradient itself - forgetting to flip and invert is the most common algebra slip here.
- Judging the nearest site by eye instead of by distance. On a diagram that isn't drawn perfectly to scale, always substitute coordinates into the distance formula (or the bisector inequality) rather than guessing from the picture.
- Assuming a boundary point is closest to every site in the diagram. A point on one edge is equidistant only to the two sites either side of that specific edge, not to every site in the whole diagram.
Using your GDC
Voronoi questions are almost entirely coordinate geometry - finding a midpoint, a perpendicular gradient, and solving two linear equations simultaneously. There's no dedicated calculator routine specific to Voronoi diagrams, but your GDC is genuinely useful for two things: evaluating distances with the distance formula once you've substituted in coordinates, and solving the pair of bisector equations simultaneously rather than by hand - most models have a simultaneous-equation solver or a "solve" command that takes two linear equations and returns the intersection point directly. Whichever calculator you use, the safest approach is still to write down the bisector equations algebraically first, then use the calculator only to evaluate or solve, so you can show full working for the method marks.
See the full GDC guide for calculator-specific instructions on solving simultaneous equations and evaluating expressions.
Ready to practise properly?
Voronoi diagram questions, marked instantly like the real exam.
Quick answers
The questions students on this topic ask most often.
Do I need to construct a Voronoi diagram from scratch?
No - the syllabus is explicit that you won't be asked to construct perpendicular bisectors by hand-drawn geometric construction. Site coordinates are given, and you calculate the bisector equations algebraically instead.
What is a Voronoi vertex?
A Voronoi vertex is a point equidistant from three (or more) sites, where three cell boundaries meet. In exam questions the solution point is always at the intersection of exactly three edges.
What is the toxic waste dump problem?
It's the classic application of finding the point as far as possible from every site within a bounded region - the ideal (or worst) location for something you want maximally distant from all the existing points. The answer is always a Voronoi vertex.
How do I add a new site to an existing Voronoi diagram?
Find the perpendicular bisector between the new site and each existing site whose cell it might cut into, then use those bisectors to redraw the boundaries. Points closer to the new site switch into its cell; everything else keeps its original nearest site.
Sub-topics
Voronoi Diagrams broken down into its individual skills, each with its own focused page.
Related topics
More Geometry & Trigonometry topics from the same AI HL syllabus unit, in case you want to keep going.