Toxic Waste Dump Problem (DP IB Applications & Interpretation (AI)): Revision Note

Toxic Waste Dump Problem

What is the toxic waste dump problem?

• The toxic waste dump problem is the name given to the general idea of finding the point on a Voronoi diagram which is furthest from any of the sites

  • A site is the coordinates of a specific place of interest on a Voronoi diagram

• It is given this name because of the common problem of finding a place to put a toxic waste dump that is equally far away from any inhabited area

  • For example, if a province contains five towns a Voronoi diagram could be used to find the point within the province which is furthest from each town

• The toxic waste dump problem is more of an idea than a specific problem

  • The same concept could be applied to other contexts such as

    • Finding a position for a new supermarket that is equally far from all competitors

    • Finding a place to plant a new tree that is equally far from other trees competing for water resources

    • Finding the quietest place to enjoy a picnic that is equally far from other noisy groups of people

  • Note that the term equally far is used in all of the above examples

How is a Voronoi diagram used to find the furthest point from any site?

• Within any Voronoi diagram the furthest point from any site will always be either

  • one of the cell vertices, or

  • somewhere on a boundary of the diagram

• In an IB exam, the solution will always be one of the cell vertices

• To find the furthest point you will need to consider each of the cell vertices separately and find which one is furthest from all of the sites

• This is done by constructing the largest empty circle

What is the largest empty circle?

• The largest empty circle is the largest possible circle constructed on a Voronoi diagram that contains no sites

• The centre of the circle will be one of the vertices of a cell or region

  • The vertices of each region are the intersections of the boundaries

• The radius of the circle will be the distance from the vertex to the closest site

  • The closest site will be on the circumference

  • Use Pythagoras’ Theorem to find the distance

• There may be a scale to convert the distance found on the Voronoi diagram into a distance in real life

  • For example if the scale is 1 unit represents 5 km then 5 units represents 25 km