Applications of Voronoi Diagrams
Nearest neighbor interpolation from a Voronoi diagram, where each cell takes the value of its generating site and points on boundaries may use an average of the adjacent sites, and toxic waste dump problems (largest empty circle) solved by finding the Voronoi vertex farthest from its nearest sites.
Nearest neighbor interpolation
Nearest neighbor interpolation is a method for estimating unknown data points based on a Voronoi diagram. If each site is assigned a numerical value, such as the precise temperature at the location of a site, then all other points in that site's cell are also approximated at that value. Points which are equidistant from two are more sites are approximated by averaging the values of the sites it is equidistant from.
Example (temperature):
The graphic shows a heat map overlaid with a Voronoi diagram split into five sections. The generating sites, denoted with black triangles, represent the exact temperatures taken at those locations. Dragging the thermostat around indicates the nearest neighbor approximation (the text on the bottom left) for the location at the thermostat's current position.
Toxic waste dump problems
The toxic waste dump problem, sometimes referred to as the largest empty circle problem, is a type of question that asks you to identify the farthest location from all other given sites. This is solved by constructing a Voronoi diagram, and the answer to the toxic waste dump problem is always a vertex of the corresponding Voronoi diagram. If there are multiple vertices, the solution is the vertex which is further from its closest sites (the one which is the center of a circle with the largest radius).
In the example above, Q is further from its closest points than P, so the solution to this toxic waste dump problem is the point Q.
This kind of problem may also appear in the context of placing businesses as far as possible from their competitors, or identifying the point at the center of the largest circle that can be drawn on a diagram without containing any of the sites.
Nice work completing Applications of Voronoi Diagrams, here's a quick recap of what we covered:
Skills covered
Exercises checked off