3.6 Voronoi diagrams
Studying this course? Keep your progress in one place.
Key facts
- A Voronoi diagram splits the plane into cells, each the region closest to one site.
- An edge lies on the perpendicular bisector of two sites.
- A vertex is where three edges meet: equidistant from three sites.
- Find the closest site by comparing (squared) distances.
- Adding a site shrinks neighbouring cells and changes edges and vertices.
- The best place for a facility far from all sites is a vertex.
Sites, cells, edges and vertices
Each cell is the region of points closer to its site than to any other.
The given points are sites (schools, weather stations, hospitals).
- A cell is the region closest to one site.
- An edge is a boundary between two cells: part of the perpendicular bisector of the two sites.
- A vertex is where edges meet; in exam questions it is always where three edges meet.
What is true of every point on an edge of a Voronoi diagram?
Equations of edges
An edge is the perpendicular bisector of two sites, and a vertex is where two edges meet.
In examinations the coordinates of the sites are given and you are not asked to construct bisectors. Sites with equal -coordinates give a vertical edge (for example and give ).
A vertex is found by solving two edge equations simultaneously.
- 1
Midpoint
of the two sites
- 2
Negative reciprocal
of the gradient joining them
- 3
Point-gradient form
Worked example
Sites are , and . Find the edge between and , and the vertex where it meets the edge between and .
- 1
Midpoint of : . Gradient of is .
- 2
The edge has gradient : , so .
- 3
The edge between and is .
- 4
Substitute : .
Sites and lie on the same vertical line. What is the edge between them?
Identifying the closest site
Calculate the distance from the point to each site and choose the smallest.
Using squared distances avoids square roots. A point on an edge is equidistant from two sites; it belongs to both cells.
- Closest sitesmallest squared distance
Worked example
Sites are , and . Which site is closest to ?
- 1
.
- 2
.
- 3
.
The squared distances from a point to sites , , are 12, 9 and 15. Which cell is the point in?
Adding a site
A new cell appears; neighbouring cells shrink and edges and vertices change.
When a new site is added, its edges are the perpendicular bisectors between it and its neighbouring sites.
Parts of the old cells are taken over by the new one. Cells of sites far from the new one may be unaffected.
Worked example
Stations and have the edge . A new station is added. Find the new edges and vertex.
- 1
Edge : midpoint , gradient of , so .
- 2
Edge : midpoint , gradient of , so .
- 3
At both give .
What happens to the cells of neighbouring sites when a new site is added?
Areas of regions
Cells are polygons: find the vertices and split the region into triangles or rectangles.
Substitute the boundary value (for example ) into an edge equation to find where an edge meets the side of the region.
Worked example
The reserve is , . Find the area of the cell of as a percentage of the reserve.
- 1
The edges meet at (from ) and (from ).
- 2
The vertices are , and : a triangle with base and height .
- 3
Area km.
- 4
Percentage: .
A triangular cell has base 10 and height 6. What is its area?
Interpolation and the waste dump
Nearest neighbour interpolation copies the closest site's value; the toxic waste dump goes at a vertex.
Nearest neighbour interpolation gives every point in a cell the value of its site (for example rainfall). in the cell of is estimated as 's reading, 80 mm, not a mean.
In the toxic waste dump problem, choose a vertex: it is furthest from its three closest sites. Other uses: urban planning, disease spread, ecology, meteorology.
Nearest neighbour interpolation
- Estimate a value from the closest site
- Same value across a whole cell
Toxic waste dump
- Place a facility as far as possible from its nearest sites
- Choose a vertex
Worked example
Villages are at , and . Find the best place for a waste dump and its distance from the nearest village.
- 1
Edge : .
- 2
Edge : midpoint , gradient of , so .
- 3
Substitute : , so the vertex is .
- 4
Distance from : .
Why is the best place for the dump at a vertex?
Try an exam question
Sites are , and . Find the equation of the edge between and and the edge between and , and hence the coordinates of the vertex.
[4 marks]
- [1] and have the same -coordinate, so the edge is horizontal.
- [1]The midpoint of is , so the edge is .
- [1]The edge between and is .
- [1]The vertex is .
That's the notes covered.
Carry on to the next subtopic.
Try a question
Find the equation of the edge between the cells of and .
1 mark, marked against the mark scheme
Find the equation of the edge between the cells of and .
1 mark, marked against the mark scheme