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

Exam Tip

The solution to the toxic waste dump will always be one of the points of intersection between the perpendicular bisectors, so you need to know the coordinates of these points
- Remember that you can use your GDC to solve a pair of the simultaneous equations quickly if you know the equations of two of the perpendicular bisectors that intersect at that point

Worked example

The Voronoi diagram below shows four cities at the sites A, B, C and D. The coordinates of the points X and Y are $(\frac{5}{4}, \frac{7}{4})$ and $(\frac{5}{2}, \frac{3}{2})$ respectively.

3-4-2-diagram-for-we-2-1

Determine the optimal position where a toxic waste site could be located and, given that 1 unit represents 50 km, find the distance from this point to its nearest city.

3-4-2-toxic-waste-dump-problem-we-solution

Toxic Waste Dump Problem (DP IB Maths: AI HL)

Revision Note