Menu
Sign up Sign in

AI HL · 12.8

Voronoi Diagrams

0 of 19 skills done

0
12.8.6

The toxic waste dump problem

12.8.6

The toxic waste dump problem

Target: I can find the point in a region that is farthest from every site by checking the vertices of the Voronoi diagram. (+4 more)

By the end of this section

Key points

The largest empty circle

  • Toxic waste dump problem: find the point in a region that is as far as possible from the nearest site. A waste site, a noisy road or a mast might all be placed this way.
  • The region must have a boundary. Without one, a point could always be moved farther away.
  • The answer is the centre of the largest circle that has no site inside it. That centre is a vertex of the Voronoi diagram, or a point on the boundary of the region.
  • A vertex is the same distance from every site round it. One distance for each vertex is enough.

The method

  • List the vertices of the Voronoi diagram that are inside the region.
  • For each vertex, find the distance to one site next to it: \(d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\). Compare squares if you like; take the square root for the final answer.
  • The vertex with the greatest distance is the best place. The distance is the radius of the largest empty circle.
  • Write the answer as a sentence: the point, and its distance from the nearest sites.

Two special cases

  • Boundary: if the region is a rectangle or polygon, also check its corners and the points where an edge meets the boundary. Each is at the distance to its nearest site. Sometimes a corner beats every vertex inside.
  • Three sites with coordinates: find two perpendicular bisectors, solve them together to get the vertex, then the distance from the vertex to any of the three sites. No diagram is needed.

On the calculator

Solving two bisectors

  • Write the two perpendicular bisectors as equations and solve them together to find the vertex.
  • Use the calculator for square roots, then round to 3 significant figures at the end.

Screenshot and video to come

Explore: the toxic waste dump

Press the vertex you think is farthest from every site. The circle round it, through its nearest sites, shows how far that is. Drag a site to change the diagram.

Press a vertex.

  1. Why is the farthest point from every site always a vertex, or a point on the boundary of the region?
  2. Press two vertices that look about equally far. How can you tell which is farther?
  3. Tick the box for the corners. When can a corner beat every vertex inside? Drag a site to make a corner win.
  4. Drag one site towards the best vertex. What happens to the largest empty circle? Why does the problem need a boundary?

Explore: build a Voronoi diagram

Drag the sites, add one or take one away, and watch the cells change. Drag the orange point P to see which site is nearest to it.

Drag a site or the point P.

  1. Drag P across an edge. What happens to the nearest site? What is true about the two distances when P is on the edge?
  2. Tick the vertices and press one. How many sites are the same distance from it? What does the dashed circle show?
  3. Add a site close to the middle of the diagram. Which cells get smaller, and which cells do not change at all?
  4. Move two sites so that they are very close together. Where is the edge between them? Why is it so short or so long?

Worked examples

Problems like the ones in class. Pick one, try it, then open the working.
The point farthest from every site

An island has 6 towns, A, B, C, D, E and F. The diagram shows their Voronoi diagram; one unit is km. A waste site is to be placed inside the region (a rectangle 9 units by 7 units), as far as possible from every town. The vertices of the diagram inside the region are P(3.5, 3.5), Q(3.75, 4), R(4, 2), S(7.5, 2). Find where the waste site should go and its distance from the nearest town.

1234567891234567xyABCDEF
Working
  1. The farthest point is a vertex

    Candidates: P(3.5, 3.5), Q(3.75, 4), R(4, 2), S(7.5, 2)

    A point inside a cell is nearer to its site than a vertex on the cell's edge could be. The largest empty circle is centred at a vertex, so you only need to check the vertices.

  2. The distance formula

    C(1, 1): \(d=\sqrt{(3.5-1)^2+(3.5-1)^2}=\sqrt{12.5}\) = 3.54

    Use the distance formula between the vertex and one site next to it. A vertex is the same distance from every site round it, so one site is enough.

  3. Every vertex

    P: 3.54; Q: 3.40; R: 3.16; S: 1.12

    Distance to a nearest site, to 3 significant figures.

  4. The greatest

    P(3.5, 3.5) is greatest: \(\sqrt{12.5}\) = 3.54

    Put the waste site at P. The circle centred there with this radius has no town inside it.

Video walkthrough coming
The distance formula

A Voronoi vertex V is at (−1, 4). A site S is at (4, −3). Find the distance from V to S.

Working
  1. The formula

    \(d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}\)

    Subtract the x-coordinates and the y-coordinates, then square each difference.

  2. Substitute

    \(d=\sqrt{(-1-4)^2+(4-(-3))^2}\)

    Put the brackets round negative numbers.

  3. Evaluate

    \(d=\sqrt{74}\) = 8.60

    Leave the square root as it is if the question wants an exact answer.

Video walkthrough coming
When the best point is a corner

A nature reserve has 5 hides, A, B, C, D and E. The diagram shows their Voronoi diagram; one unit is km. A waste site is to be placed inside the region (a rectangle 9 units by 7 units), as far as possible from every hide. The vertices inside the region are P(4, 5), Q(5.5, 3.5), R(7.5, 5.5). The waste site may be anywhere in the region, including its boundary. Find where it should go and its distance from the nearest hide.

1234567891234567xyABCDE
Working
  1. Check the vertices

    P: 1; Q: 1.58; R: 2.55

    Greatest vertex distance: 2.55.

  2. The boundary points

    (0, 0): 5.66; (0, 1): 5; (0, 7): 3.61; (4, 7): 2.24; (4.33, 0): 4.01; (7.5, 0): 3.04; (8.5, 7): 4.03; (9, 0): 3.16; (9, 7): 4.12

    The region has a boundary, so also check its corners and the points where an edge meets it. Each is a distance to its nearest site.

  3. The greatest

    (0, 0): \(\sqrt{32}\) = 5.66

    This is greater than every vertex inside. The best place is the corner of the region at (0, 0), not a vertex.

Video walkthrough coming
Three sites from their coordinates

Three ranger stations, A(−7, 5), B(−1, −7) and C(5, −7), are in a national park. One unit is 10 km. The Voronoi diagram is shown. Find the point where a waste site is farthest from all three ranger stations, assuming it is the vertex of the diagram, and its distance from them.

−8−6−4−22468−8−6−4−22468xyABC
Working
  1. Bisector of A and B

    \(y=\dfrac{1}{2}x+1\)

    Through the midpoint of A and B, perpendicular to AB.

  2. Bisector of B and C

    \(x=2\)

    The vertex is on both bisectors.

  3. Solve together

    From the calculator: x = 2, y = 2

    The vertex is (2, 2).

  4. The distance

    A(−7, 5): \(d=\sqrt{(2-(-7))^2+(2-5)^2}=\sqrt{90}\) = 9.49

    The vertex is the same distance from A, B and C. This is the radius of the largest empty circle.

Video walkthrough coming