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

• 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

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 is one of the vertices of a cell

  • The radius of the circle is 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

How do I use a Voronoi diagram to find the furthest point from any of the sites?

• The furthest point from any of the sites is always either

  • at one of the vertices of the cells

  • somewhere on a boundary of the diagram

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

• To find the furthest point:

  • Find the largest empty circle centred at each vertex

  • Choose the vertex whose largest empty circle has the biggest radius

• This is done by constructing the largest empty circle