Toxic Waste Dump problem
'Can Voronoi diagrams help us select a site that is as far as possible from all existing sites?'
Russia’s Kamchatka peninsula has one of the highest densities of volcanoes in the world. The map, in the 'Resources' section below shows the rough positions of four volcanoes. A new hotel, with observation posts, is planned in the area below. The developers want to build it not further than 80km from each of the 4 volcanoes (so as to have a good reasonable view of all of them), but at a point that is as far as possible, given this condition (1 unit = 20km). Which position meets this criteria?
Aims
This activity aims to help students develop their own, conceptual understanding of the "toxic waste dump (aka largest circle) problem". It provides a concrete means (the applets in the 'Resource' section) through which they can experiment, using their current knowledge, get feedback, and gradually move towards an appreciation, and understanding, of the voronoi approach.
Resources - 1
Brainstorm the question above using the applet below. You can add points, measure lengths/distances, construct circles, perpendicular bisectors, mid-points etc.
Resources - 2: Optimal solution?
The below applet illustrates the voronoi diagram for these four volcano sites. Change the position of the "MoveMe" point to confirm that point "I" does satisfy the hotel developers requirements: "not further than 80km from each of the 4 volcanoes (so as to have a good reasonable view of all of them), but at a point that is as far as possible from each, given this condition (1 unit = 20km)".
The distances from the points "Moveme" and "I" to each volcano are shown so that you can compare if the requirements are satisfied, or not.
You can add points, measure lengths/distances, construct circles and find mid-points using the tools available at the top of the applet, if you would like to test that point "I" really is the optimal solution.
IB Learner Profile - Thinker/Reflective
What line is the "MoveMe" point following?
Explain why is it not necessary to experiment with points that do not lie on this line.
From the solution found to the problem above, what would you hypothesise as a 'general solution' to all such: 'toxic waste dump (largest circle)' problems?
IB Learner Profile - Thinker/Reflective
Why was it necessary to include, in the question, the condition that the new hotel "not be further than 80km from each of the 4 volcanoes".?
What would the coordinates of the solution be if this condition were not included? Not a mathematics question (using commercial/economics knowledge): Why might this solution not be of interest to the hotel developer?
Resources - 3: Where's Safest?
Brainstorm the question above using the applet below. You can add points, measure lengths/distances, construct circles, perpendicular bisectors, mid-points etc.
Syllabus links
Voronoi diagrams
New - Section 3.6
Description
- Students experiement with the first applet. Depending on whether this activity/parts of this activity are used prior to learning something about voronoi diagrams will likely influence the methods and approaches applied in the first applet. The aims of the first applet are to provide concrete feedback for students on their existing knowledge and motivate a need for the use of a voronoi diagram (though some may realise this for themselves!).
- The aim of the second applet is to gain an appreciation and understanding of how voronoi diagrams help solve this type of problem. It should, hopefully, also encourage students to use the solution to this one problem to speculate/hypothesise/conjecture as to the general solution for all such problems . . .