IB DP Maths: AI HL复习笔记3.5.2 Toxic Waste Dump Problem
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
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
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.
转载自savemyexams
热门国际竞赛真题资料-免费领取！
欧几里得竞赛 寒假集训班开课了！
USACO寒假集训来袭！点击咨询！
