What is Voronoi Diagram?
What is Voronoi Diagram?
A Voronoi diagram is a mathematical diagram that divides a plane into areas that are close to each of a given set of objects.
In the most basic scenario, these objects are simply a finite number of points in the plane (called seeds, sites, or generators).
There is a comparable region, known as a Voronoi cell, for each seed, which consists of all points of the plane that are closer to that seed than to any other. A collection of points’ Voronoi diagram is the inverse of its Delaunay triangulation.
The Voronoi diagram, also known as a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation, is named after Georgy Voronoy (after Peter Gustav Lejeune Dirichlet). Thiessen polygons are another name for Voronoi cells.
Voronoi diagrams have practical and theoretical applications in a wide range of industries, most notably science and technology, but also visual art.
History and investigation
The use of Voronoi diagrams in informal settings can be dated back to Descartes in 1644. In 1850, Peter Gustav Lejeune Dirichlet studied quadratic forms using two-dimensional and three-dimensional Voronoi diagrams.
In 1854, British physician John Snow developed a Voronoi-like figure to show how the vast majority of persons who died in the Broad Street cholera outbreak resided closer to the infected Broad Street pump than to any other water pump.
Georgy Feodosievych Voronoy, who defined and analyzed the general n-dimensional case in 1908, is the name given to Voronoi diagrams.
Thiessen polygons are named after American meteorologist Alfred H. Thiessen and are used in geophysics and meteorology to analyze spatially scattered data (such as rainfall measurements).
Other names for this concept (or specific key situations of it) include Voronoi polyhedra, Voronoi polygons, domain(s) of effect, Voronoi decomposition, Voronoi tessellation(s), and Dirichlet tessellation (s).
Examples
Many familiar tessellations arise from Voronoi tessellations of regular lattices of points in two or three dimensions.
- A 2D lattice produces an irregular honeycomb tessellation, with equal hexagons with point symmetry; in the case of a regular triangular lattice, it is regular; in the case of a rectangular lattice, the hexagons reduce to rectangles in rows and columns; and a square lattice produces a regular tessellation of squares; note that rectangles and squares can also be produced by other lattices
- The cubic honeycomb is formed by a simple cubic lattice.
- A tessellation of space with trapezo-rhombic dodecahedra is produced by a hexagonal close-packed lattice.
- A face-centered cubic lattice produces a space tessellation with rhombic dodecahedra.
- The hexagonal prismatic honeycomb is formed by parallel planes with regular triangular lattices aligned with each other’s centers.
Computation
We can begin to compute the Voronoi diagram now that we have a clear explanation of what it is.
Many algorithms will perform the job; however, the simplest one to comprehend needs us to first compute the Delaunay triangulation of our set of points, rather than the Voronoi diagram.
But what precisely is the Delaunay triangulation, and how does it help us identify the Voronoi diagram? It’s a set of triangles constructed with our original set of points as vertices.
However, there is one condition. The vertex of no triangle in the formation shall be inside the circumcircle of other triangles in the formation.
But what precisely is the Delaunay triangulation, and how does it help us identify the Voronoi diagram? It’s a set of triangles constructed with our original set of points as vertices. However, there is one condition.
The vertex of no triangle in the formation shall be inside the circumcircle of other triangles in the formation. As an example, consider the following structure:
That is why, if we already have a Delaunay triangulation, we only need to discover the edges of our Voronoi graph by constructing an edge from the circumcenter of each surrounding triangle to its own circumcenter.
So, how do we calculate the Delaunay triangulation now? Using the Bowyer-Watson algorithm is one method.
This procedure works by adding points to an existing Delaunay triangulation repeatedly, usually starting with a very simple triangulation that encloses all of the points to be triangulated.
We check after each insertion to see whether any triangles’ circumcircles include the new point, and if so, we delete them, leaving a cavity and then joining the vertices on the cavity boundaries.
Generalizations and variations
Voronoi cells, as the name implies, can be defined for metrics other than Euclidean, such as the Mahalanobis distance or Manhattan distance.
However, the bounds of the Voronoi cells in these circumstances may be more problematic than in the Euclidean case, because the equidistant locus for two points may fail to be a codimension 1 subspace, even in the two-dimensional example.
A weighted Voronoi diagram is one in which the function of a pair of points used to create a Voronoi cell is a distance function that has been changed by multiplicative or additive weights assigned to generator points.
In contrast to the case of Voronoi cells specified by a metric distance, some of the Voronoi cells in this case may be empty.
A power diagram is a sort of Voronoi diagram defined by a set of circles using the power distance; it can alternatively be thought of as a weighted Voronoi diagram in which a weight specified by each circle’s radius is added to the squared Euclidean distance from the circle’s center.
The vertices of a Voronoi diagram of n points in d-dimensional space can be text style O(nlceil d/2rceil ), needing the same bound for the amount of memory required to store an explicit description of it.
As a result, Voronoi diagrams are frequently impractical at moderate or high dimensions. Approximate Voronoi diagrams are a more space-efficient option.
Applications of Voronoi diagrams
Meteorology/Hydrology
It is used in meteorology and engineering hydrology to calculate the weights for precipitation data from stations spread throughout an area (watershed).
The points that generate the polygons are the numerous stations that record precipitation data. Perpendicular bisectors are drawn to the line connecting any two stations. As a result, polygons form around the stations.
Humanities
The symmetry of statue heads is examined in classical archaeology, specifically art history, to establish the type of statue a severed head may have belonged to. The identification of the Sabouroff head, which used a high-resolution Polygon mesh, is an example of this using Voronoi cells.
Voronoi cells are employed in dialectometry to illustrate a presumed linguistic continuity between survey points.
Natural sciences
Voronoi diagrams are used in biology to model a variety of biological structures, such as cells and bone microarchitecture. Indeed, Voronoi tessellations can be used as a geometrical tool to better comprehend the physical limitations that govern the formation of biological tissues.
In hydrology, Voronoi diagrams are used to compute the rainfall of an area based on a sequence of point observations. In this context, they are commonly referred to as Thiessen polygons.
In computational chemistry, ligand-binding sites are translated into Voronoi diagrams for machine learning applications (e.g., to classify binding pockets in proteins).
In other applications, Voronoi cells formed by the positions of the nuclei in a molecule are used to determine atomic charges. This is accomplished through the use of the Voronoi deformation density approach.
Voronoi diagrams are used in ecology to investigate the growth patterns of forests and forest canopies, and they may also be useful in constructing forecasting models for forest fires.
Health
Models of muscle tissue based on Voronoi diagrams can be used in medical diagnosis to detect neuromuscular illnesses.
In epidemiology, Voronoi diagrams can be used to link the sources of illnesses in epidemics. John Snow used Voronoi diagrams to examine the 1854 Broad Street cholera outbreak in Soho, England.
He drew a line on a map of Central London connecting the residential areas whose residents used a specific water pump and the areas with the highest number of deaths from the outbreak.
Engineering
Voronoi diagrams can be used to illustrate free volumes of polymers in polymer physics.
As an aircraft advances through its flight plan, Voronoi diagrams are superimposed on oceanic plotting maps to find the nearest airfield for in-flight diversion (see ETOPS).
Geometry
On top of the Voronoi diagram, a point location data structure can be developed to answer nearest neighbor queries, which seek the object that is closest to a given query point.
Nearest neighbor inquiries offer a wide range of uses. For example, one may wish to locate the nearest hospital or the most similar thing in a database. Vector quantization, which is often employed in data compression, is a large application.
In geometry, Voronoi diagrams can be used to identify the greatest empty circle among a group of points and in an enclosing polygon; for example, to build a new supermarket as far away from all existing ones in a given city as possible.
Bakery
Dinara Kasko, a Ukrainian pastry maker, shapes her original desserts using the mathematical concepts of the Voronoi diagram and silicone molds manufactured with a 3D printer.
Planning and civics
In Melbourne, government school pupils are always entitled to attend the closest primary or high school to their home, as defined by a straight-line distance. As a result, the school zone map is a Voronoi diagram.
Algorithms
There are several efficient procedures for creating Voronoi diagrams, either directly (as the diagram) or indirectly (by starting with a Delaunay triangulation and then deriving its dual). Fortune’s algorithm, an O (n log(n)) approach for producing a Voronoi diagram from a set of points in a plane, is an example of a direct algorithm.
The Bowyer–Watson algorithm, which generates a Delaunay triangulation in any number of dimensions in O (n log(n)) to O(n2) time, can be utilized in an indirect algorithm for the Voronoi diagram.
The Jump Flooding Algorithm is suitable for use on commodity graphics technology and can build approximation Voronoi diagrams in constant time.
Lloyd’s algorithm, and its generalization via the Linde–Buzo–Gray algorithm (aka k-means clustering), employ Voronoi diagram creation as a subroutine.
These approaches alternate between phases in which the Voronoi diagram for a collection of seed points is constructed and steps in which the seed points are relocated to more central locations within their cells.
These approaches can be employed in any space to iteratively converge towards a specific form of the Voronoi diagram known as a Centroidal Voronoi tessellation, in which the sites have been shifted to positions that are also the geometric centers of their cells.
Voronoi diagrams FAQs
What is a Voronoi Diagram?
A Voronoi diagram is a mathematical diagram that divides a plane into areas that are close to each of a given set of objects. In their most basic form, these objects are simply a finite number of points in the plane (referred to as seeds, sites, or generators).
Thiessen polygons are another name for Voronoi cells.
What is Voronoi diagram used for?
Thiessen polygon maps, also known as Voronoi diagrams, are used to construct and delineate proximal regions around individual data points using polygonal bounds.
What do Voronoi diagrams have to do with cholera?
Assume you have a number of sites (such as the water pumps in Snow’s maps) scattered across a mappable area.
These locations are represented by dots on a voronoi diagram, and the points on the diagram’s edges are exactly those spots that are equidistant between two (or more if you are on a region’s corner).
What is the voronoi line John Snow?
Snow then considered the city’s drinking water sources, pumps, and drew a line labeled “Boundary of equal distance between Broad Street Pump and other Pumps,” which effectively denoted the Voronoi cell of the Broad Street Pump.
What is the difference between the voronoi and Thiessen polygons?
Thiessen polygons are named after American meteorologist Alfred H. Thiessen and are used in geophysics and meteorology to analyze spatially scattered data (such as rainfall measurements).
Why is Voronoi present in nature?
A Voronoi pattern reveals nature’s proclivity toward efficiency: the nearest neighbor, shortest path, and tightest fit. A seed point exists in each cell of a Voronoi pattern. Everything within a cell is more closely related to it than to any other seed.
What did the Voronoi diagram fail to account for?
The Voronoi diagram fails owing to self-intersecting polygons.
What are Thiessen polygons used for?
Thiessen polygons are commonly used in geography, computer science, and other disciplines. Thiessen polygons are most commonly used in human geography to identify dominant regions or service areas for point data, such as stores or hospitals.
Who created the Voronoi diagram?
Voronoi diagrams were proposed by René Descartes in 1644 and are named after the Russian mathematician Georgy Voronoi, who defined and investigated the general n-dimensional case in 1908. This diagram is made by randomly distributing points on a Euclidean plane.
What are the 5 patterns in nature?
Spiral, meander, explosion, packing, and branching are the “Five Patterns in Nature” that we choose to investigate.
How do you calculate Voronoi diagram?
The Voronoi diagram for the set S = s1, s2 is made up of two half-planes separated by the perpendicular bisector of s1s2, ray l. It should be noted that the two zones are not disjoint, but rather overlap at the set of points on the ray l that are equidistant from both places.
