Did this video help you?
Toxic Waste Dump Problem (DP IB Maths: AI HL)
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
- The same concept could be applied to other contexts such as
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
Examiner 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 and respectively.
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.
You've read 0 of your 10 free revision notes
Unlock more, it's free!
Did this page help you?