3.6 Voronoi diagrams
Studying this course? Keep your progress in one place.
Key facts
- A Voronoi diagram splits a plane into cells, each the region closest to one site.
- An edge is part of the perpendicular bisector of two sites; a vertex is where three edges meet.
- Compare squared distances to find the closest site.
- Adding a site shrinks neighbouring cells and changes edges and vertices.
- Nearest-neighbour interpolation uses the closest site only; a vertex is the best place for a "toxic waste dump".
Sites, cells, edges and vertices
It divides a plane by which site is closest, with edges on perpendicular bisectors and vertices equidistant from three sites.
A Voronoi diagram divides a plane into regions according to which of a set of points is closest.
The given points are sites (schools, weather stations, hospitals). Each cell is the region closer to its site than to any other. An edge is a boundary between two cells, part of the perpendicular bisector of the sites. A vertex is where three edges meet: it is equidistant from three sites.
- 1
Sites
the given points
- 2
Edges
perpendicular bisectors between pairs of sites
- 3
Vertices
where three edges meet
- 4
Cells
the regions the edges enclose, one per site
A vertex of a Voronoi diagram is equidistant from...
Equations of edges
An edge is the perpendicular bisector of the two sites; a vertex comes from solving two edge equations.
In examinations the coordinates of the sites are given and you are not asked to construct bisectors. You may be asked for the equation of a boundary: find the perpendicular bisector of the two sites (midpoint, negative reciprocal gradient, ).
Sites with equal -coordinates give a vertical edge: , give .
A vertex is found by solving two edge equations: and give .
Worked example
Sites are A(2, 1) and C(6, 9). Find the equation of the edge between their cells.
- 1
Midpoint: .
- 2
Gradient of , so the edge has gradient .
- 3
Use .
Sites and . The edge between them is...
The closest site
Calculate the squared distance to each site and choose the smallest.
To decide which site is closest to a point , calculate the distance from 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.
- Squared distance
Worked example
Sites are P(1, 2), Q(7, 2) and R(4, 8). Which site is closest to X(5, 3)?
- 1
.
- 2
.
- 3
.
Squared distances to three sites are 12, 7, 20. X is in the cell of...
Adding a site
A new cell appears and neighbouring cells shrink; old edges stop at new vertices.
When a new site is added, a new cell appears around it. Its edges are the perpendicular bisectors between the new site and its neighbouring sites. Parts of the old cells are taken over, so neighbouring cells shrink; cells of far-off sites may be unaffected.
Stations and have the edge . A new station creates edges (with ) and (with ), meeting at . The edge now exists only below this vertex.
A new site is added. What happens to neighbouring cells?
Areas of regions
Find the coordinates of its vertices and split it into triangles or rectangles.
Cells are polygons, so find the coordinates of the vertices and split the region into triangles or rectangles.
Substitute the boundary value (here ) into an edge equation to find where an edge meets the side of the region.
For a percentage of the reserve, divide the cell area by the whole area and multiply by 100.
Worked example
Find the area of the cell of R₃ as a percentage of the reserve. Its vertices are (6, 3.875), (0.5, 8) and (11.5, 8).
- 1
Base along : .
- 2
Height: .
- 3
Area: km.
- 4
Reserve area: , so the percentage is .
A triangle has base 11 and height 4.125. Its area is...
Interpolation and the toxic waste dump
Nearest-neighbour interpolation copies the closest site's value; the furthest-from-everything point is a vertex.
Nearest neighbour interpolation estimates a value at a point using the value at the closest site: every point in a cell gets its site's value. If is in the cell of , the rainfall is estimated as 's reading, 80 mm, not a mean of readings.
Toxic waste dump problem: to place a facility as far as possible from its nearest site, choose a vertex. Find it by solving two edge equations, then the distance to a site.
Other uses: urban planning, disease spread, ecology, meteorology and resource management.
Where do you place a dump as far as possible from three villages?
Try an exam question
Sites , and are used to draw a Voronoi diagram. Find the equation of the edge between the cells of and , and the coordinates of the vertex where the three edges meet.
[4 marks]
- [1]Midpoint of and gradient of .
- [1]Edge gradient , so , i.e. .
- [1]The edge between and is .
- [1]Vertex: , so .
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