3.6 Voronoi diagrams

3.6 Voronoi diagrams

IB Maths: Applications and Interpretation SL: Revision notes

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. 1

    Sites

    the given points

  2. 2

    Edges

    perpendicular bisectors between pairs of sites

  3. 3

    Vertices

    where three edges meet

  4. 4

    Cells

    the regions the edges enclose, one per site

How the parts fit together

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, y−y1=m(x−x1)y-y_1=m(x-x_1)).

Sites with equal yy-coordinates give a vertical edge: A(2,1)A(2,1), B(10,1)B(10,1) give x=6x=6.

A vertex is found by solving two edge equations: x=6x=6 and y=−12x+7y=-\frac12x+7 give (6,4)(6,4).

x = 6ABCV
Sites A(2, 1), B(10, 1), C(6, 9): the edges meet at the vertex (6, 4)

Worked example

Sites are A(2, 1) and C(6, 9). Find the equation of the edge between their cells.

Sites (2,1)(2,1) and (10,1)(10,1). 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 XX, calculate the distance from XX 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.

d² = 8d² = 5A (1, 1)B (5, 2)X (3, 3)
Point X is closer to site B: d² = 5 to B and 8 to A, so X lies in B's cell.
  • Squared distance(x2−x1)2+(y2−y1)2(x_2-x_1)^2+(y_2-y_1)^2

Worked example

Sites are P(1, 2), Q(7, 2) and R(4, 8). Which site is closest to X(5, 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 R1(3,3)R_1(3,3) and R2(9,3)R_2(9,3) have the edge x=6x=6. A new station R3(6,7)R_3(6,7) creates edges y=−0.75x+8.375y=-0.75x+8.375 (with R1R_1) and y=0.75x−0.625y=0.75x-0.625 (with R2R_2), meeting x=6x=6 at (6,3.875)(6,3.875). The edge x=6x=6 now exists only below this vertex.

x = 6R1R2R3V
Before the new site, the edge is x = 6. R₃(6, 7) creates a vertex at (6, 3.875)

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 y=8y=8) 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.

114.125VPQR3
The cell of R₃ in the reserve 0 ≤ x ≤ 12, 0 ≤ y ≤ 8 is a triangle

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).

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 X(5,3)X(5,3) is in the cell of QQ, the rainfall is estimated as QQ'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.

4.474.474.47V1V2V3D
Villages V₁(0, 0), V₂(8, 0), V₃(2, 6): the vertex (4, 2) is √20 = 4.47 km from each

Where do you place a dump as far as possible from three villages?

Try an exam question

Sites A(2,1)A(2,1), B(10,1)B(10,1) and C(6,9)C(6,9) are used to draw a Voronoi diagram. Find the equation of the edge between the cells of AA and CC, and the coordinates of the vertex where the three edges meet.

[4 marks]

That's the notes covered.

Carry on to the next subtopic.

Try a question

Find the equation of the edge between the cells of AA and BB.

1 mark, marked against the mark scheme

Revision notes