Voronoi Diagram - Applications

Applications

• In epidemiology, Voronoi diagrams can be used to correlate sources of infections in epidemics. One of the early applications of Voronoi diagrams was in fact by John Snow to study the 1854 Broad Street cholera outbreak in Soho, England. He showed the correlation between areas on the map of London using a particular water pump, and the areas with most deaths due to the outbreak.

• A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications. For example, one might want to find the nearest hospital, or the most similar object in a database. A large application is vector quantization, commonly used in data compression.

• In geometry, Voronoi diagrams can be used to find the largest empty circle amid a set of points, and in an enclosing polygon; e.g. to build a new supermarket as far as possible from all the existing ones, lying in a certain city.

• Voronoi diagrams together with farthest-point Voronoi diagrams are used for efficient algorithms to compute the roundness of a set of points.

• The Voronoi approach is also put to good use in the evaluation of circularity / roundness while assesing the dataset from a Coordinate-measuring machine.

• In polymer physics, Voronoi diagrams can be used to represent free volumes of polymers.

• In networking, Voronoi diagrams can be used in derivations of the capacity of a wireless network.

• In climatology, Voronoi diagrams are used to calculate the rainfall of an area, based on a series of point measurements. In this usage, they are generally referred to as Thiessen polygons.

• In ecology, Voronoi diagrams are used to study the growth patterns of forests and forest canopies, and may also be helpful in developing predictive models for forest fires.

• In computer graphics, Voronoi diagrams are used to procedurally generate of organic-looking textures.

• In autonomous robot navigation, Voronoi diagrams are used to find clear routes. If the points are obstacles, then the edges of the graph will be the routes furthest from obstacles (and theoretically any collisions).

• In computational chemistry, Voronoi cells defined by the positions of the nuclei in a molecule are used to compute atomic charges. This is done using the Voronoi deformation density method.

• In materials science, polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations.

• In mining, Voronoi polygons are used to estimate the reserves of valuable materials, minerals or other resources. Exploratory drillholes are used as the set of points in the Voronoi polygons.

• In machine learning, Voronoi diagrams are used to do 1-NN classifications.