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 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?
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
In your groups, brainstorm some ideas you may have on how to approach/work towards a solution for the 'hotel' question above using the applet below and your existing mathematical knowledge and reasoning. You can add points, measure lengths/distances, construct circles, perpendicular bisectors, mid-points etc.
If you team/group gets really stuck, click on the "EYE" icon below HINTS underneath this applet.
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 it is 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?
Resources - 3: Where's Safest?
Is the solution shown in applet 2 really "the safest place to be" on the mapped area shown? Use the applet below to experiment if there are other places that are safer than this solution. . You can add points, measure lengths/distances, construct circles, perpendicular bisectors, mid-points etc as required.
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? Why might this solution not be of interest to the hotel developer?[Not a mathematics question (using commercial/economics knowledge)]
- Students experiment 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 . . .
- The third applet provides an opportunity to test if the solution shown in applet 2 really is "the safest place to be" on the mapped area shown.