3.6 Voronoi diagrams

3.6 Voronoi diagrams

IB Maths: Applications and Interpretation HL: Revision notes

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.
ABC
Three sites A, B, C. The three edges meet at the vertex (6, 4).

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 yy-coordinates give a vertical edge (for example A(2,1)A(2,1) and B(10,1)B(10,1) give x=6x=6).

A vertex is found by solving two edge equations simultaneously.

  1. 1

    Midpoint

    of the two sites

  2. 2

    Negative reciprocal

    of the gradient joining them

  3. 3

    Point-gradient form

    y−y1=m(x−x1)y-y_1=m(x-x_1)

Equation of an edge.

Worked example

Sites are A(2,1)A(2,1), B(10,1)B(10,1) and C(6,9)C(6,9). Find the edge between AA and CC, and the vertex where it meets the edge between AA and BB.

Sites P(1,3)P(1,3) and Q(1,9)Q(1,9) 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 P(1,2)P(1,2), Q(7,2)Q(7,2) and R(4,8)R(4,8). Which site is closest to X(5,3)X(5,3)?

The squared distances from a point to sites S1S_1, S2S_2, S3S_3 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.

R1R2R3
Adding R3 gives a new vertex at (6, 3.875). The old edge x = 6 now stops there.

Worked example

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) is added. Find the new edges and vertex.

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 y=8y=8) into an edge equation to find where an edge meets the side of the region.

11VLR
The cell of R3 in the reserve 0 ≤ x ≤ 12, 0 ≤ y ≤ 8 is a triangle.

Worked example

The reserve is 0≤x≤120\le x\le12, 0≤y≤80\le y\le8. Find the area of the cell of R3R_3 as a percentage of the reserve.

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). X(5,3)X(5,3) in the cell of QQ is estimated as QQ'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 V1(0,0)V_1(0,0), V2(8,0)V_2(8,0) and V3(2,6)V_3(2,6). Find the best place for a waste dump and its distance from the nearest village.

Why is the best place for the dump at a vertex?

Try an exam question

Sites are A(0,0)A(0,0), B(8,0)B(8,0) and C(0,6)C(0,6). Find the equation of the edge between AA and CC and the edge between AA and BB, and hence the coordinates of the vertex.

[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