In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, a Voronoi diagram is a
partition
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of a ...
of a
plane
Plane(s) most often refers to:
* Aero- or airplane, a powered, fixed-wing aircraft
* Plane (geometry), a flat, 2-dimensional surface
Plane or planes may also refer to:
Biology
* Plane (tree) or ''Platanus'', wetland native plant
* ''Planes' ...
into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding
region
In geography, regions, otherwise referred to as zones, lands or territories, are areas that are broadly divided by physical characteristics (physical geography), human impact characteristics (human geography), and the interaction of humanity and t ...
, called a Voronoi cell, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is
dual to that set's
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
.
The Voronoi diagram is named after mathematician
Georgy Voronoy
Georgy Feodosevich Voronoy (russian: Георгий Феодосьевич Вороной; ukr, Георгій Феодосійович Вороний; 28 April 1868 – 20 November 1908) was an Russian Empire, Imperial Russian mathematician of U ...
, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
). Voronoi cells are also known as Thiessen polygons. Voronoi diagrams have practical and theoretical applications in many fields, mainly in
science
Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earliest archeological evidence for ...
and
technology
Technology is the application of knowledge to reach practical goals in a specifiable and reproducible way. The word ''technology'' may also mean the product of such an endeavor. The use of technology is widely prevalent in medicine, science, ...
, but also in
visual art
The visual arts are art forms such as painting, drawing, printmaking, sculpture, ceramics, photography, video, filmmaking, design, crafts and architecture. Many artistic disciplines such as performing arts, conceptual art, and textile arts ...
.
The simplest case
In the simplest case, shown in the first picture, we are given a finite set of points in the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
. In this case each site ''p''
''k'' is simply a point, and its corresponding Voronoi cell ''R''
''k'' consists of every point in the Euclidean plane whose distance to ''p''
''k'' is less than or equal to its distance to any other ''p''
''k''. Each such cell is obtained from the intersection of
half-spaces, and hence it is a
(convex) polyhedron. The
line segment
In geometry, a line segment is a part of a straight line that is bounded by two distinct end points, and contains every point on the line that is between its endpoints. The length of a line segment is given by the Euclidean distance between ...
s of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines, ...
s) are the points equidistant to three (or more) sites.
Formal definition
Let
be a
metric space
In mathematics, a metric space is a set together with a notion of ''distance'' between its elements, usually called points. The distance is measured by a function called a metric or distance function. Metric spaces are the most general settin ...
with distance function
. Let
be a set of indices and let
be a
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
(ordered collection) of nonempty
subsets (the sites) in the space
. The Voronoi cell, or Voronoi region,
, associated with the site
is the set of all points in
whose distance to
is not greater than their distance to the other sites
, where
is any index different from
. In other words, if
denotes the distance between the point
and the subset
, then
The Voronoi diagram is simply the
tuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...
of cells
. In principle, some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in
geometry of numbers Geometry of numbers is the part of number theory which uses geometry for the study of algebraic numbers. Typically, a ring of algebraic integers is viewed as a lattice in \mathbb R^n, and the study of these lattices provides fundamental information ...
and
crystallography
Crystallography is the experimental science of determining the arrangement of atoms in crystalline solids. Crystallography is a fundamental subject in the fields of materials science and solid-state physics (condensed matter physics). The wor ...
), but again, in many cases only finitely many sites are considered.
In the particular case where the space is a
finite-dimensional
In mathematics, the dimension of a vector space ''V'' is the cardinality (i.e., the number of vectors) of a basis of ''V'' over its base field. p. 44, §2.36 It is sometimes called Hamel dimension (after Georg Hamel) or algebraic dimension to disti ...
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are
convex polytope
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...
s and they can be represented in a combinatorial way using their vertices, sides, two-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. In general however, the Voronoi cells may not be convex or even connected.
In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon
is associated with a generator point
.
Let
be the set of all points in the Euclidean space. Let
be a point that generates its Voronoi region
,
that generates
, and
that generates
, and so on. Then, as expressed by Tran ''et al'',
"all locations in the Voronoi polygon are closer to the generator point of that polygon than any other generator point in the Voronoi diagram in Euclidean plane".
Illustration
As a simple illustration, consider a group of shops in a city. Suppose we want to estimate the number of customers of a given shop. With all else being equal (price, products, quality of service, etc.), it is reasonable to assume that customers choose their preferred shop simply by distance considerations: they will go to the shop located nearest to them. In this case the Voronoi cell
of a given shop
can be used for giving a rough estimate on the number of potential customers going to this shop (which is modeled by a point in our city).
For most cities, the distance between points can be measured using the familiar
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
:
:
or the
Manhattan distance
A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or Metric (mathematics), metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences ...
:
:
.
The corresponding Voronoi diagrams look different for different distance metrics.
Properties
* The
dual graph
In the mathematical discipline of graph theory, the dual graph of a plane graph is a graph that has a vertex for each face of . The dual graph has an edge for each pair of faces in that are separated from each other by an edge, and a self-loop ...
for a Voronoi diagram (in the case of a
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's Elements, Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics ther ...
with point sites) corresponds to the
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
for the same set of points.
* The
closest pair of points
The closest pair of points problem or closest pair problem is a problem of computational geometry: given n points in metric space, find a pair of points with the smallest distance between them. The closest pair problem for points in the Euclidean ...
corresponds to two adjacent cells in the Voronoi diagram.
* Assume the setting is the
Euclidean plane
In mathematics, the Euclidean plane is a Euclidean space of dimension two. That is, a geometric setting in which two real quantities are required to determine the position of each point ( element of the plane), which includes affine notions of ...
and a discrete set of points is given. Then two points of the set are adjacent on the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
if and only if their Voronoi cells share an infinitely long side.
* If the space is a
normed space
In mathematics, a normed vector space or normed space is a vector space over the real or complex numbers, on which a norm is defined. A norm is the formalization and the generalization to real vector spaces of the intuitive notion of "length" i ...
and the distance to each site is attained (e.g., when a site is a
compact set
In mathematics, specifically general topology, compactness is a property that seeks to generalize the notion of a closed and bounded subset of Euclidean space by making precise the idea of a space having no "punctures" or "missing endpoints", i ...
or a closed ball), then each Voronoi cell can be represented as a union of line segments emanating from the sites.
[.] As shown there, this property does not necessarily hold when the distance is not attained.
* Under relatively general conditions (the space is a possibly infinite-dimensional
uniformly convex space In mathematics, uniformly convex spaces (or uniformly rotund spaces) are common examples of reflexive Banach spaces. The concept of uniform convexity was first introduced by James A. Clarkson in 1936.
Definition
A uniformly convex space is a ...
, there can be infinitely many sites of a general form, etc.) Voronoi cells enjoy a certain stability property: a small change in the shapes of the sites, e.g., a change caused by some translation or distortion, yields a small change in the shape of the Voronoi cells. This is the geometric stability of Voronoi diagrams.
[.] As shown there, this property does not hold in general, even if the space is two-dimensional (but non-uniformly convex, and, in particular, non-Euclidean) and the sites are points.
History and research
Informal use of Voronoi diagrams can be traced back to
Descartes in 1644.
Peter Gustav Lejeune Dirichlet
Johann Peter Gustav Lejeune Dirichlet (; 13 February 1805 – 5 May 1859) was a German mathematician who made deep contributions to number theory (including creating the field of analytic number theory), and to the theory of Fourier series and ...
used two-dimensional and three-dimensional Voronoi diagrams in his study of quadratic forms in 1850.
British physician
John Snow
John Snow (15 March 1813 – 16 June 1858) was an English physician and a leader in the development of anaesthesia and medical hygiene. He is considered one of the founders of modern epidemiology, in part because of his work in tracing the so ...
used a Voronoi-like diagram in 1854 to illustrate how the majority of people who died in the
Broad Street cholera outbreak
Broad(s) or The Broad(s) may refer to:
People
* A slang term for a woman.
* Broad (surname), a surname
Places
* Broad Peak, on the border between Pakistan and China, the 12th highest mountain on Earth
* The Broads, a network of mostly nav ...
lived closer to the infected
Broad Street pump
Soho is an area of the City of Westminster, part of the West End of London. Originally a fashionable district for the aristocracy, it has been one of the main entertainment districts in the capital since the 19th century.
The area was develo ...
than to any other water pump.
Voronoi diagrams are named after
Georgy Feodosievych Voronoy who defined and studied the general ''n''-dimensional case in 1908. Voronoi diagrams that are used in
geophysics
Geophysics () is a subject of natural science concerned with the physical processes and physical properties of the Earth and its surrounding space environment, and the use of quantitative methods for their analysis. The term ''geophysics'' som ...
and
meteorology
Meteorology is a branch of the atmospheric sciences (which include atmospheric chemistry and physics) with a major focus on weather forecasting. The study of meteorology dates back millennia, though significant progress in meteorology did not ...
to analyse spatially distributed data (such as rainfall measurements) are called Thiessen polygons after American meteorologist
Alfred H. Thiessen. Other equivalent names for this concept (or particular important cases of it): Voronoi polyhedra, Voronoi polygons, domain(s) of influence, Voronoi decomposition, Voronoi tessellation(s), Dirichlet tessellation(s).
Examples
Voronoi tessellations of regular
lattice
Lattice may refer to:
Arts and design
* Latticework, an ornamental criss-crossed framework, an arrangement of crossing laths or other thin strips of material
* Lattice (music), an organized grid model of pitch ratios
* Lattice (pastry), an orna ...
s of points in two or three dimensions give rise to many familiar tessellations.
* A 2D lattice gives 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; a
square
In Euclidean geometry, a square is a regular quadrilateral, which means that it has four equal sides and four equal angles (90-degree angles, π/2 radian angles, or right angles). It can also be defined as a rectangle with two equal-length adj ...
lattice gives the regular tessellation of squares; note that the rectangles and the squares can also be generated by other lattices (for example the lattice defined by the vectors (1,0) and (1/2,1/2) gives squares).
* A
simple cubic lattice
In crystallography, the cubic (or isometric) crystal system is a crystal system where the unit cell is in the shape of a cube. This is one of the most common and simplest shapes found in crystals and minerals.
There are three main varieties o ...
gives the
cubic honeycomb
The cubic honeycomb or cubic cellulation is the only proper regular space-filling tessellation (or honeycomb) in Euclidean 3-space made up of cubic cells. It has 4 cubes around every edge, and 8 cubes around each vertex. Its vertex figure is a re ...
.
* A
hexagonal close-packed
In geometry, close-packing of equal spheres is a dense arrangement of congruent spheres in an infinite, regular arrangement (or lattice). Carl Friedrich Gauss proved that the highest average density – that is, the greatest fraction of space occu ...
lattice gives a tessellation of space with
trapezo-rhombic dodecahedra.
* A
face-centred cubic
In crystallography, the cubic (or isometric) crystal system is a crystal system where the unit cell is in the shape of a cube. This is one of the most common and simplest shapes found in crystals and minerals.
There are three main varieties of ...
lattice gives a tessellation of space with
rhombic dodecahedra
Rhombic may refer to:
*Rhombus, a quadrilateral whose four sides all have the same length (often called a diamond)
*Rhombic antenna, a broadband directional antenna most commonly used on shortwave frequencies
* polyhedra formed from rhombuses, such ...
.
* A
body-centred cubic
In crystallography, the cubic (or isometric) crystal system is a crystal system where the unit cell is in the shape of a cube. This is one of the most common and simplest shapes found in crystals and minerals.
There are three main varieties of ...
lattice gives a tessellation of space with
truncated octahedra
In geometry, the truncated octahedron is the Archimedean solid that arises from a regular octahedron by removing six pyramids, one at each of the octahedron's vertices. The truncated octahedron has 14 faces (8 regular hexagon, hexagons and 6 Squa ...
.
* Parallel planes with regular triangular lattices aligned with each other's centers give the
hexagonal prismatic honeycomb
The triangular prismatic honeycomb or triangular prismatic cellulation is a space-filling tessellation (or honeycomb) in Euclidean 3-space. It is composed entirely of triangular prisms.
It is constructed from a triangular tiling extruded into pri ...
.
* Certain body-centered tetragonal lattices give a tessellation of space with
rhombo-hexagonal dodecahedra.
For the set of points (''x'', ''y'') with ''x'' in a discrete set ''X'' and ''y'' in a discrete set ''Y'', we get rectangular tiles with the points not necessarily at their centers.
Higher-order Voronoi diagrams
Although a normal Voronoi cell is defined as the set of points closest to a single point in ''S'', an ''n''th-order Voronoi cell is defined as the set of points having a particular set of ''n'' points in ''S'' as its ''n'' nearest neighbors. Higher-order Voronoi diagrams also subdivide space.
Higher-order Voronoi diagrams can be generated recursively. To generate the ''n''
th-order Voronoi diagram from set ''S'', start with the (''n'' − 1)
th-order diagram and replace each cell generated by ''X'' = with a Voronoi diagram generated on the set ''S'' − ''X''.
Farthest-point Voronoi diagram
For a set of ''n'' points the (''n'' − 1)
th-order Voronoi diagram is called a farthest-point Voronoi diagram.
For a given set of points ''S'' = the farthest-point Voronoi diagram divides the plane into cells in which the same point of ''P'' is the farthest point. A point of ''P'' has a cell in the farthest-point Voronoi diagram if and only if it is a vertex of the
convex hull
In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of ''P''. Let ''H'' = be the convex hull of ''P''; then the farthest-point Voronoi diagram is a subdivision of the plane into ''k'' cells, one for each point in ''H'', with the property that a point ''q'' lies in the cell corresponding to a site ''h''
''i'' if and only if d(''q'', ''h''
''i'') > d(''q'', ''p''
''j'') for each ''p''
''j'' ∈ ''S'' with ''h''
''i'' ≠ ''p''
''j'', where d(''p'', ''q'') is the
Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...
between two points ''p'' and ''q''.
[ 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.]
The boundaries of the cells in the farthest-point Voronoi diagram have the structure of a
topological tree, with infinite
rays
Ray may refer to:
Fish
* Ray (fish), any cartilaginous fish of the superorder Batoidea
* Ray (fish fin anatomy), a bony or horny spine on a fin
Science and mathematics
* Ray (geometry), half of a line proceeding from an initial point
* Ray (gra ...
as its leaves. Every finite tree is isomorphic to the tree formed in this way from a farthest-point Voronoi diagram.
Generalizations and variations
As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean, such as the
Mahalanobis distance or
Manhattan distance
A taxicab geometry or a Manhattan geometry is a geometry whose usual distance function or Metric (mathematics), metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences ...
. However, in these cases the boundaries of the Voronoi cells may be more complicated than in the Euclidean case, since the equidistant locus for two points may fail to be subspace of codimension 1, even in the two-dimensional case.
A
weighted Voronoi diagram
In mathematics, a weighted Voronoi diagram in ''n'' dimensions is a generalization of a Voronoi diagram. The Voronoi cells in a weighted Voronoi diagram are defined in terms of a distance function. The distance function may specify the usual Eucl ...
is the one in which the function of a pair of points to define a Voronoi cell is a distance function modified by multiplicative or additive weights assigned to generator points. In contrast to the case of Voronoi cells defined using a distance which is a
metric
Metric or metrical may refer to:
* Metric system, an internationally adopted decimal system of measurement
* An adjective indicating relation to measurement in general, or a noun describing a specific type of measurement
Mathematics
In mathem ...
, in this case some of the Voronoi cells may be empty. A
power diagram
In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from ...
is a type of Voronoi diagram defined from a set of circles using the
power distance
Power distance is a dimension theorized and proven by Geert Hofstede, who outlined multiple cultural dimensions throughout his work. This term refers to inequality and unequal distributions of power between parties; whether it is within the work ...
; it can also be thought of as a weighted Voronoi diagram in which a weight defined from the radius of each circle is added to the
squared Euclidean distance
In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two Point (geometry), points.
It can be calculated from the Cartesian coordinates of the points using the Pythagorean theo ...
from the circle's center.
The Voronoi diagram of
points in
-dimensional space can have
vertices, requiring the same bound for the amount of memory needed to store an explicit description of it. Therefore, Voronoi diagrams are often not feasible for moderate or high dimensions. A more space-efficient alternative is to use
approximate Voronoi diagrams.
Voronoi diagrams are also related to other geometric structures such as the
medial axis
The medial axis of an object is the set of all points having more than one closest point on the object's boundary. Originally referred to as the topological skeleton, it was introduced in 1967 by Harry Blum as a tool for biological shape recogn ...
(which has found applications in image segmentation,
optical character recognition
Optical character recognition or optical character reader (OCR) is the electronic or mechanical conversion of images of typed, handwritten or printed text into machine-encoded text, whether from a scanned document, a photo of a document, a scen ...
, and other computational applications),
straight skeleton
In geometry, a straight skeleton is a method of representing a polygon by a topological skeleton. It is similar in some ways to the medial axis but differs in that the skeleton is composed of straight line segments, while the medial axis of a pol ...
, and
zone diagrams.
Applications
Meteorology/Hydrology
It is used in meteorology and engineering hydrology to find the weights for precipitation data of stations over an area (watershed). The points generating the polygons are the various station that record precipitation data. Perpendicular bisectors are drawn to the line joining any two stations. This results in the formation of polygons around the stations. The area
touching station point is known as influence area of the station. The average precipitation is calculated by the formula
Humanities
*In
classical archaeology
Classical archaeology is the archaeological investigation of the Mediterranean civilizations of Ancient Greece and Ancient Rome. Nineteenth-century archaeologists such as Heinrich Schliemann were drawn to study the societies they had read about i ...
, specifically
art history
Art history is the study of aesthetic objects and visual expression in historical and stylistic context. Traditionally, the discipline of art history emphasized painting, drawing, sculpture, architecture, ceramics and decorative arts; yet today ...
, the symmetry of
statue
A statue is a free-standing sculpture in which the realistic, full-length figures of persons or animals are carved or cast in a durable material such as wood, metal or stone. Typical statues are life-sized or close to life-size; a sculpture t ...
heads is analyzed to determine the type of statue a severed head may have belonged to. An example of this that made use of Voronoi cells was the identification of the
Sabouroff head
The Sabouroff head is a Late Archaic Greece, Archaic Greek marble sculpture. It is dated to circa 550 BC, 550–525 BC. This head of a Kouros was named after Peter Alexandrovich Saburov, a collector of ancient Greek sculpture and antiquities. It i ...
, which made use of a high-resolution
polygon mesh
In 3D computer graphics and solid modeling, a polygon mesh is a collection of , s and s that defines the shape of a polyhedral object. The faces usually consist of triangles (triangle mesh), quadrilaterals (quads), or other simple convex polyg ...
.
*In
dialectometry
Dialectometry is the quantitative and computational branch of dialectology, the study of dialect. This sub-field of linguistics studies language variation using the methods of statistics; it arose in the 1970s and 80s as a result of seminal work ...
, Voronoi cells are used to indicate a supposed linguistic continuity between survey points.
Natural sciences
![Voronoi growth euclidean](https://upload.wikimedia.org/wikipedia/commons/d/d9/Voronoi_growth_euclidean.gif)
*In
biology
Biology is the scientific study of life. It is a natural science with a broad scope but has several unifying themes that tie it together as a single, coherent field. For instance, all organisms are made up of cells that process hereditary i ...
, Voronoi diagrams are used to model a number of different biological structures, including
cells and
bone microarchitecture. Indeed, Voronoi tessellations work as a geometrical tool to understand the physical constraints that drive the organization of biological tissues.
*In
hydrology
Hydrology () is the scientific study of the movement, distribution, and management of water on Earth and other planets, including the water cycle, water resources, and environmental watershed sustainability. A practitioner of hydrology is calle ...
, 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
Ecology () is the study of the relationships between living organisms, including humans, and their physical environment. Ecology considers organisms at the individual, population, community, ecosystem, and biosphere level. Ecology overlaps wi ...
, 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
computational chemistry
Computational chemistry is a branch of chemistry that uses computer simulation to assist in solving chemical problems. It uses methods of theoretical chemistry, incorporated into computer programs, to calculate the structures and properties of m ...
, ligand-binding sites are transformed into Voronoi diagrams for
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
applications (e.g., to classify binding pockets in proteins). In other applications, 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
astrophysics
Astrophysics is a science that employs the methods and principles of physics and chemistry in the study of astronomical objects and phenomena. As one of the founders of the discipline said, Astrophysics "seeks to ascertain the nature of the h ...
, Voronoi diagrams are used to generate adaptative smoothing zones on images, adding signal fluxes on each one. The main objective of these procedures is to maintain a relatively constant
signal-to-noise ratio
Signal-to-noise ratio (SNR or S/N) is a measure used in science and engineering that compares the level of a desired signal to the level of background noise. SNR is defined as the ratio of signal power to the noise power, often expressed in deci ...
on all the images.
*In
computational fluid dynamics
Computational fluid dynamics (CFD) is a branch of fluid mechanics that uses numerical analysis and data structures to analyze and solve problems that involve fluid flows. Computers are used to perform the calculations required to simulate th ...
, the Voronoi tessellation of a set of points can be used to define the computational domains used in
finite volume methods, e.g. as in the moving-mesh cosmology code AREPO.
*In
computational physics
Computational physics is the study and implementation of numerical analysis to solve problems in physics for which a quantitative theory already exists. Historically, computational physics was the first application of modern computers in science, ...
, Voronoi diagrams are used to calculate profiles of an object with
Shadowgraph
Shadowgraph is an optical method that reveals non-uniformities in transparent media like air, water, or glass. It is related to, but simpler than, the schlieren and schlieren photography methods that perform a similar function. Shadowgraph is a ty ...
and proton radiography in
High energy density physics High-energy-density physics (HEDP) is a new subfield of physics intersecting condensed matter physics, nuclear physics, astrophysics and plasma physics. It has been defined as the physics of matter and radiation at energy densities in excess of a ...
.
Health
*In
medical diagnosis
Medical diagnosis (abbreviated Dx, Dx, or Ds) is the process of determining which disease or condition explains a person's symptoms and signs. It is most often referred to as diagnosis with the medical context being implicit. The information re ...
, models of muscle tissue, based on Voronoi diagrams, can be used to detect neuromuscular diseases.
*In
epidemiology
Epidemiology is the study and analysis of the distribution (who, when, and where), patterns and determinants of health and disease conditions in a defined population.
It is a cornerstone of public health, and shapes policy decisions and evidenc ...
, Voronoi diagrams can be used to correlate sources of infections in epidemics. One of the early applications of Voronoi diagrams was implemented by
John Snow
John Snow (15 March 1813 – 16 June 1858) was an English physician and a leader in the development of anaesthesia and medical hygiene. He is considered one of the founders of modern epidemiology, in part because of his work in tracing the so ...
to study the
1854 Broad Street cholera outbreak
Events
January–March
* January 4 – The McDonald Islands are discovered by Captain William McDonald aboard the ''Samarang''.
* January 6 – The fictional detective Sherlock Holmes is perhaps born.
* January 9 – The ...
in Soho, England. He showed the correlation between residential areas on the map of Central London whose residents had been using a specific water pump, and the areas with the most deaths due to the outbreak.
Engineering
*In
polymer physics, Voronoi diagrams can be used to represent free volumes of polymers.
*In
materials science, polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations. In island growth, the Voronoi diagram is used to estimate the growth rate of individual islands.
In
solid-state physics
Solid-state physics is the study of rigid matter, or solids, through methods such as quantum mechanics, crystallography, electromagnetism, and metallurgy. It is the largest branch of condensed matter physics. Solid-state physics studies how the l ...
, the
Wigner-Seitz cell is the Voronoi tessellation of a solid, and the
Brillouin zone
In mathematics and solid state physics, the first Brillouin zone is a uniquely defined primitive cell in reciprocal space. In the same way the Bravais lattice is divided up into Wigner–Seitz cells in the real lattice, the reciprocal lattice i ...
is the Voronoi tessellation of reciprocal (
wavenumber
In the physical sciences, the wavenumber (also wave number or repetency) is the ''spatial frequency'' of a wave, measured in cycles per unit distance (ordinary wavenumber) or radians per unit distance (angular wavenumber). It is analogous to temp ...
) space of crystals which have the symmetry of a space group.
*In
aviation
Aviation includes the activities surrounding mechanical flight and the aircraft industry. ''Aircraft'' includes fixed-wing and rotary-wing types, morphable wings, wing-less lifting bodies, as well as lighter-than-air craft such as hot air ...
, Voronoi diagrams are superimposed on oceanic plotting charts to identify the nearest airfield for in-flight diversion (see
ETOPS
ETOPS () is an acronym for ''Extended-range Twin-engine Operations Performance Standards''—a special part of flight rules for one-engine-inoperative flight conditions. The International Civil Aviation Organization (ICAO) coined the acronym for ...
), as an aircraft progresses through its flight plan.
*In
architecture
Architecture is the art and technique of designing and building, as distinguished from the skills associated with construction. It is both the process and the product of sketching, conceiving, planning, designing, and constructing building ...
, Voronoi patterns were the basis for the winning entry for the redevelopment of
The Arts Centre Gold Coast
Home of the Arts (HOTA), opened as the Keith Hunt Community Entertainment and Arts Centre in 1986 and subsequently renamed The Arts Centre Gold Coast (TAC) and Gold Coast Arts Centre, is a cultural precinct situated in Surfers Paradise, City of ...
.
*In
urban planning
Urban planning, also known as town planning, city planning, regional planning, or rural planning, is a technical and political process that is focused on the development and design of land use and the built environment, including air, water, ...
, Voronoi diagrams can be used to evaluate the Freight Loading Zone system.
*In
mining
Mining is the extraction of valuable minerals or other geological materials from the Earth, usually from an ore body, lode, vein, seam, reef, or placer deposit. The exploitation of these deposits for raw material is based on the economic via ...
, 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
surface metrology
Surface metrology is the measurement of small-scale features on surfaces, and is a branch of metrology. Surface primary form, surface Fractal dimension, fractality, and surface finish (including surface roughness) are the parameters most commonly a ...
, Voronoi tessellation can be used for
surface roughness
Surface roughness, often shortened to roughness, is a component of surface finish (surface texture). It is quantified by the deviations in the direction of the normal vector of a real surface from its ideal form. If these deviations are large, ...
modeling.
*In
robotics
Robotics is an interdisciplinary branch of computer science and engineering. Robotics involves design, construction, operation, and use of robots. The goal of robotics is to design machines that can help and assist humans. Robotics integrat ...
, some of the control strategies and path planning algorithms of
multi-robot systems
A multi-agent system (MAS or "self-organized system") is a computerized system composed of multiple interacting intelligent agents.Hu, J.; Bhowmick, P.; Jang, I.; Arvin, F.; Lanzon, A.,A Decentralized Cluster Formation Containment Framework fo ...
are based on the Voronoi partitioning of the environment.
Geometry
*A
point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided ...
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
In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
. A large application is
vector quantization
Vector quantization (VQ) is a classical quantization technique from signal processing that allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by di ...
, commonly used in
data compression
In information theory, data compression, source coding, or bit-rate reduction is the process of encoding information using fewer bits than the original representation. Any particular compression is either lossy or lossless. Lossless compression ...
.
*In
geometry
Geometry (; ) is, with arithmetic, one of the oldest branches of mathematics. It is concerned with properties of space such as the distance, shape, size, and relative position of figures. A mathematician who works in the field of geometry is c ...
, Voronoi diagrams can be used to find the
largest empty circle
In computational geometry, the largest empty sphere problem is the problem of finding a hypersphere of largest radius in ''d''-dimensional space whose interior does not overlap with any given obstacles.
Two dimensions
The largest empty circl ...
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
Roundness is the measure of how closely the shape of an object approaches that of a mathematically perfect circle. Roundness applies in two-dimensional space, two dimensions, such as the cross section (geometry), cross sectional circles along a c ...
of a set of points.
The Voronoi approach is also put to use in the evaluation of circularity/
roundness
Roundness is the measure of how closely the shape of an object approaches that of a mathematically perfect circle. Roundness applies in two-dimensional space, two dimensions, such as the cross section (geometry), cross sectional circles along a c ...
while assessing the dataset from a
coordinate-measuring machine
A coordinate measuring machine (CMM) is a device that measures the geometry of physical objects by sensing discrete points on the surface of the object with a probe. Various types of probes are used in CMMs, the most common being mechanical and l ...
.
Informatics
*In
networking, Voronoi diagrams can be used in derivations of the capacity of a
wireless network
A wireless network is a computer network that uses wireless data connections between network nodes.
Wireless networking is a method by which homes, telecommunications networks and business installations avoid the costly process of introducing c ...
.
*In
computer graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, cell phone and computer displays, and many specialized applications. A great de ...
, Voronoi diagrams are used to calculate 3D shattering / fracturing geometry patterns. It is also used to
procedurally generate organic or lava-looking textures.
* In autonomous
robot navigation
Robot localization denotes the robot's ability to establish its own position and orientation within the frame of reference. Path planning is effectively an extension of localisation, in that it requires the determination of the robot's current pos ...
, 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
machine learning
Machine learning (ML) is a field of inquiry devoted to understanding and building methods that 'learn', that is, methods that leverage data to improve performance on some set of tasks. It is seen as a part of artificial intelligence.
Machine ...
, Voronoi diagrams are used to do
1-NN classifications.
*In global scene reconstruction, including with random sensor sites and unsteady wake flow, geophysical data, and 3D turbulence data, Voronoi tesselations are used with
deep learning
Deep learning (also known as deep structured learning) is part of a broader family of machine learning methods based on artificial neural networks with representation learning. Learning can be supervised, semi-supervised or unsupervised.
De ...
.
*In
user interface
In the industrial design field of human–computer interaction, a user interface (UI) is the space where interactions between humans and machines occur. The goal of this interaction is to allow effective operation and control of the machine f ...
development, Voronoi patterns can be used to compute the best hover state for a given point.
Civics and planning
* In
Melbourne
Melbourne ( ; Boonwurrung/Woiwurrung: ''Narrm'' or ''Naarm'') is the capital and most populous city of the Australian state of Victoria, and the second-most populous city in both Australia and Oceania. Its name generally refers to a met ...
, government school students are always eligible to attend the nearest primary school or high school to where they live, as measured by a straight-line distance. The map of school zones is therefore a Voronoi diagram.
Bakery
* Ukrainian Pastry chef
Dinara Kasko uses the mathematical principles of the Voronoi diagram to create silicone molds made with a 3D printer to shape her original cakes.
Algorithms
Several efficient algorithms are known for constructing Voronoi diagrams, either directly (as the diagram itself) or indirectly by starting with a
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
and then obtaining its dual.
Direct algorithms include
Fortune's algorithm
Fortune's algorithm is a sweep line algorithm for generating a Voronoi diagram from a set of points in a plane using O(''n'' log ''n'') time and O(''n'') space. Section 7.2: Computing the Voronoi Diagram: pp.151–160. It was origina ...
, an
O(''n'' log(''n'')) algorithm for generating a Voronoi diagram from a set of points in a plane.
Bowyer–Watson algorithm
In computational geometry, the Bowyer–Watson algorithm is a method for computing the Delaunay triangulation of a finite set of points in any number of dimensions. The algorithm can be also used to obtain a Voronoi diagram of the points, which is ...
, an
O(''n'' log(''n'')) to
O(''n''
2) algorithm for generating a Delaunay triangulation in any number of dimensions, can be used in an indirect algorithm for the Voronoi diagram. The
Jump Flooding Algorithm can generate approximate Voronoi diagrams in constant time and is suited for use on commodity graphics hardware.
Lloyd's algorithm In electrical engineering and computer science, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm named after Stuart P. Lloyd for finding evenly spaced sets of points in subsets of Euclidean spaces and partitions of t ...
and its generalization via the
Linde–Buzo–Gray algorithm
The Linde–Buzo–Gray algorithm (introduced by Yoseph Linde, Andrés Buzo and Robert M. Gray in 1980) is a vector quantization algorithm to derive a good codebook.
It is similar to the k-means method in data clustering.
The algorithm
At each ...
(aka
k-means clustering), use the construction of Voronoi diagrams as a subroutine.
These methods alternate between steps in which one constructs the Voronoi diagram for a set of seed points, and steps in which the seed points are moved to new locations that are more central within their cells. These methods can be used in spaces of arbitrary dimension to iteratively converge towards a specialized form of the Voronoi diagram, called a
Centroidal Voronoi tessellation, where the sites have been moved to points that are also the geometric centers of their cells.
See also
*
Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation (also known as a Delone triangulation) for a given set P of discrete points in a general position is a triangulation DT(P) such that no point in P is inside the circumcircle o ...
*
Map segmentation
*
Natural element method
*
Natural neighbor interpolation
image:Natural-neighbors-coefficients-example.png, 200px, Natural neighbor interpolation with Sibson weights. The area of the green circles are the interpolating weights, ''w'i''. The purple-shaded region is the new Voronoi cell, after inserting ...
*
Nearest-neighbor interpolation
Nearest-neighbor interpolation (also known as proximal interpolation or, in some contexts, point sampling) is a simple method of multivariate interpolation in one or more dimensions.
Interpolation is the problem of approximating the value of ...
*
Power diagram
In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from ...
*
Voronoi pole
In geometry, the positive and negative Voronoi poles of a cell in a Voronoi diagram are certain vertices of the diagram.
Definition
Let V be the Voronoi diagram for a set of sites P, and let V_p be the Voronoi cell of V corresponding to a site ...
Notes
References
*
*
* ''Includes a description of Fortune's algorithm.''
*
*
*
*
*
*
*
*
External links
*
Voronoi Diagramsin
CGAL
The Computational Geometry Algorithms Library (CGAL) is an open source software library of computational geometry algorithms. While primarily written in C++, Scilab bindings and bindings generated with SWIG (supporting Python and Java for now) ar ...
, the Computational Geometry Algorithms Library
{{DEFAULTSORT:Voronoi Diagram
Discrete geometry
Computational geometry
Diagrams
Ukrainian inventions
Russian inventions