Content
Applications of Voronoi Diagrams
A deeper dive into common uses of Voronoi diagrams on the IB exam
A deeper dive into common uses of Voronoi diagrams on the IB exam
No exercises available for this concept.
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.
Powered by Desmos
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).
Powered by Desmos
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.