In
mathematicsMathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a
Voronoi diagram is a special kind of decomposition of a given space, e.g., a
metric spaceIn mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
, determined by distances to a specified family of objects (subsets) in the space. These objects are usually called the sites or the generators (but other names such as "seeds" are in use) and to each such an object one associates a corresponding Voronoi cell, namely the set of all
points in the given space whose distance to the given object is not greater than their distance to the other objects. It is named after
Georgy VoronoiGeorgy Feodosevich Voronoy was a Russian Empire mathematician of Ukrainian origin. Among other things, he defined the Voronoi diagram.Voronoy was born in the village of Zhuravky, district of Pyriatin, in Poltava Governorate of the Russian Empire .From 1889, Voronoy studied at Saint Petersburg...
, and is also called a
Voronoi tessellationA tessellation or tiling of the plane is a pattern of plane figures that fills the plane with no overlaps and no gaps. One may also speak of tessellations of parts of the plane or of other surfaces. Generalizations to higher dimensions are also possible. Tessellations frequently appeared in the art...
, a
Voronoi decomposition, or a
Dirichlet tessellation (after
Lejeune DirichletJohann Peter Gustav Lejeune Dirichlet was a German mathematician with deep contributions to number theory , as well as to the theory of Fourier series and other topics in mathematical analysis; he is credited with being one of the first mathematicians to give the modern formal definition of a...
). Voronoi diagrams can be found in a large number of fields in
scienceScience is a systematic enterprise that builds and organizes knowledge in the form of testable explanations and predictions about the universe...
and
technologyTechnology is the making, usage, and knowledge of tools, machines, techniques, crafts, systems or methods of organization in order to solve a problem or perform a specific function. It can also refer to the collection of such tools, machinery, and procedures. The word technology comes ;...
, even in
artArt is the product or process of deliberately arranging items in a way that influences and affects one or more of the senses, emotions, and intellect....
, and they have found numerous practical and theoretical applications.
The simplest case
In the simplest and most familiar case (shown in the first picture), we are given a finite set of points
{p1,...,pn} in the Euclidean plane. In this case
each site
pk is simply a point, and its corresponding Voronoi cell (also called Voronoi region or Dirichlet cell)
Rk consisting of all points whose distance to
pk is not greater than their distance to any other site. Each such cell is obtained from the intersection of half-spaces, and hence it is a
convex'The word convex means curving out or bulging outward, as opposed to concave. Convex or convexity may refer to:Mathematics:* Convex set, a set of points containing all line segments between each pair of its points...
polygonIn geometry a polygon is a flat shape consisting of straight lines that are joined to form a closed chain orcircuit.A polygon is traditionally a plane figure that is bounded by a closed path, composed of a finite sequence of straight line segments...
. The segments of the Voronoi diagram are all the points in the plane that are equidistant to the two nearest sites. The Voronoi vertices (nodes) are the points equidistant to three (or more) sites.
Formal definition
Let
X be a space (a nonempty
setA set is a collection of well defined and distinct objects, considered as an object in its own right. Sets are one of the most fundamental concepts in mathematics. Developed at the end of the 19th century, set theory is now a ubiquitous part of mathematics, and can be used as a foundation from...
) endowed with a distance function
d. Let
K be a set of indices and
let
(Pk)k ∈ K be a
tupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
(ordered collection) of nonempty subsets (the sites) in the space
X. The Voronoi cell, or Voronoi region,
Rk, associated with the site
Pk is the set of all points in
X whose distance to
Pk is not greater than their distance to the other sites
Pj , where j is any index different from k. In other words, if
d(x,A)=inf{d(x,a): a in A} denotes the distance between the point x and the subset A, then
Rk={x in X: d(x,Pk) ≤ d(x,Pj) for all j≠k}.
The Voronoi diagram is simply the
tupleIn mathematics and computer science, a tuple is an ordered list of elements. In set theory, an n-tuple is a sequence of n elements, where n is a positive integer. There is also one 0-tuple, an empty sequence. An n-tuple is defined inductively using the construction of an ordered pair...
of cells
(Rk)k ∈ K . 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 numbersIn number theory, the geometry of numbers studies convex bodies and integer vectors in n-dimensional space. The geometry of numbers was initiated by ....
and
crystallographyCrystallography is the experimental science of the arrangement of atoms in solids. The word "crystallography" derives from the Greek words crystallon = cold drop / frozen drop, with its meaning extending to all solids with some degree of transparency, and grapho = write.Before the development of...
), but again, in many cases only finitely many sites are considered.
In the particular case where the space is a finite dimensional
Euclidean spaceIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are
convex'The word convex means curving out or bulging outward, as opposed to concave. Convex or convexity may refer to:Mathematics:* Convex set, a set of points containing all line segments between each pair of its points...
polytopes and they can be represented in a combinatorial way using their vertices, sides, 2-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. However, in general the Voronoi cells may not be convex or even connected.
Illustration
As a simple illustration, consider a group of shops in a flat 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
Rk
of a given shop
Pk can be used for giving a rough estimate on the number of potential customers going to this shop (which is modeled by point in our flat city).
So far it was assumed that the distance between points in the city are measured using the standard distance, namely the
Euclidean distanceIn mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
:
d((a1,a2),(b1,b2))=((a1-b1)2+(a2-b2)2)0.5. However, if we consider the case where customers only go to the shops
by a vehicle and the traffic paths are parallel to the x and y axes, like in
ManhattanManhattan is the oldest and the most densely populated of the five boroughs of New York City. Located primarily on the island of Manhattan at the mouth of the Hudson River, the boundaries of the borough are identical to those of New York County, an original county of the state of New York...
, then a more realistic distance function will be the
l1 distanceTaxicab geometry, considered by Hermann Minkowski in the 19th century, is a form of geometry in which the usual distance function or metric of Euclidean geometry is replaced by a new metric in which the distance between two points is the sum of the absolute differences of their coordinates...
, namely
d((a1,a2),(b1,b2))=|a1-b1|+|a2-b2|.
Properties
- The dual graph
In mathematics, the dual graph of a given planar graph G is a graph which has a vertex for each plane region of G, and an edge for each edge in G joining two neighboring regions, for a certain embedding of G. The term "dual" is used because this property is symmetric, meaning that if H is a dual...
for a Voronoi diagram (in the case of a Euclidean spaceIn mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
with point sites) corresponds to the Delaunay triangulationIn mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
for the same set of points.
- The closest pair of points corresponds to two adjacent cells in the Voronoi diagram.
- Assume the setting is the Euclidean plane and a group of different points are given. Then two points are adjacent on the convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
if and only if their Voronoi cells share an infinitely long side.
- If the space is a normed space and the distance to each site is attained (e.g., when a site is a compact set 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 are common examples of reflexive Banach spaces. The concept of uniform convexity was first introduced by James 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
Informal use of Voronoi diagrams can be traced back to Descartes in 1644.
DirichletJohann Peter Gustav Lejeune Dirichlet was a German mathematician with deep contributions to number theory , as well as to the theory of Fourier series and other topics in mathematical analysis; he is credited with being one of the first mathematicians to give the modern formal definition of a...
used 2-dimensional and 3-dimensional Voronoi diagrams in his study of quadratic forms in 1850. British physician
John SnowJohn Snow was an English physician and a leader in the adoption of anaesthesia and medical hygiene. He is considered to be one of the fathers of epidemiology, because of his work in tracing the source of a cholera outbreak in Soho, England, in 1854.-Early life and education:Snow was born 15 March...
used a Voronoi diagram in 1854 to illustrate how the majority of people who died in the
Soho cholera epidemicThe Broad Street cholera outbreak was a severe outbreak of cholera that occurred near Broad Street in Soho district of London, England in 1854...
lived closer to the infected Broad Street pump than to any other water pump.
Voronoi diagrams are named after Russian mathematician
Georgy Fedoseevich VoronoiGeorgy Feodosevich Voronoy was a Russian Empire mathematician of Ukrainian origin. Among other things, he defined the Voronoi diagram.Voronoy was born in the village of Zhuravky, district of Pyriatin, in Poltava Governorate of the Russian Empire .From 1889, Voronoy studied at Saint Petersburg...
(or
Voronoy) who defined and studied the general
n-dimensional case in 1908. Voronoi diagrams that are used in
geophysicsGeophysics is the physics of the Earth and its environment in space; also the study of the Earth using quantitative physical methods. The term geophysics sometimes refers only to the geological applications: Earth's shape; its gravitational and magnetic fields; its internal structure and...
and
meteorologyMeteorology is the interdisciplinary scientific study of the atmosphere. Studies in the field stretch back millennia, though significant progress in meteorology did not occur until the 18th century. The 19th century saw breakthroughs occur after observing networks developed across several countries...
to analyse spatially distributed data (such as rainfall measurements) are called
Thiessen polygons after American meteorologist
Alfred H. ThiessenAlfred H. Thiessen was an American meteorologist after whom Thiessen polygons are named.Alfred H. Thiessen was born in Troy, New York. He earned a BS from Cornell University in 1898. His service in the Weather Bureau began at Pittsburgh as observer on July 1, 1898...
. In
condensed matter physicsCondensed matter physics deals with the physical properties of condensed phases of matter. These properties appear when a number of atoms at the supramolecular and macromolecular scale interact strongly and adhere to each other or are otherwise highly concentrated in a system. The most familiar...
, such tessellations are also known as Wigner-Seitz unit cells. Voronoi tessellations of the
reciprocal latticeIn physics, the reciprocal lattice of a lattice is the lattice in which the Fourier transform of the spatial function of the original lattice is represented. This space is also known as momentum space or less commonly k-space, due to the relationship between the Pontryagin duals momentum and...
of
momentaIn classical mechanics, linear momentum or translational momentum is the product of the mass and velocity of an object...
are called
Brillouin zoneIn mathematics and solid state physics, the first Brillouin zone is a uniquely defined primitive cell in reciprocal space. The boundaries of this cell are given by planes related to points on the reciprocal lattice. It is found by the same method as for the Wigner–Seitz cell in the Bravais lattice...
s. For general lattices in
Lie groupIn mathematics, a Lie group is a group which is also a differentiable manifold, with the property that the group operations are compatible with the smooth structure...
s, the cells are simply called
fundamental domainIn geometry, the fundamental domain of a symmetry group of an object is a part or pattern, as small or irredundant as possible, which determines the whole object based on the symmetry. More rigorously, given a topological space and a group acting on it, the images of a single point under the group...
s. In the case of general
metric spaceIn mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
s, the cells are often called metric
fundamental polygonIn mathematics, each closed surface in the sense of geometric topology can be constructed from an even-sided oriented polygon, called a fundamental polygon, by pairwise identification of its edges....
s.
Examples
Voronoi tessellations of regular
latticeIn mathematics, especially in geometry and group theory, a lattice in Rn is a discrete subgroup of Rn which spans the real vector space Rn. Every lattice in Rn can be generated from a basis for the vector space by forming all linear combinations with integer coefficients...
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 geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...
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). See here for a dynamic visual example.
- A simple cubic lattice gives the cubic honeycomb
The cubic honeycomb is the only regular space-filling tessellation 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 regular octahedron....
.
- A hexagonal close-packed lattice gives a tesselation of space with trapezo-rhombic dodecahedra
The trapezo-rhombic dodecahedron is a convex polyhedron with 6 rhombic and 6 trapezoidal faces.This shape could be constructed by taking a tall uniform hexagonal prism, and making 3 angled cuts on the top and bottom...
.
- A face-centred cubic lattice gives a tessellation of space with rhombic dodecahedra
In geometry, the rhombic dodecahedron is a convex polyhedron with 12 rhombic faces. It is an Archimedean dual solid, or a Catalan solid. Its dual is the cuboctahedron.-Properties:...
.
- A body-centred cubic lattice gives a tessellation of space with truncated octahedra
In geometry, the truncated octahedron is an Archimedean solid. It has 14 faces , 36 edges, and 24 vertices. Since each of its faces has point symmetry the truncated octahedron is a zonohedron....
.
- Parallel planes with regular triangular lattices aligned with each others' centers give the hexagonal prismatic honeycomb
The hexagonal prismatic honeycomb is a space-filling tessellation in Euclidean 3-space made up of hexagonal prisms.It is constructed from a hexagonal tiling extruded into prisms.It is one of 28 convex uniform honeycombs.- References :...
.
- Certain body centered tetragonal lattices give a tessellation of space with rhombo-hexagonal dodecahedra
The rhombo-hexagonal dodecahedron is a convex polyhedron with 8 rhombic and 4 equilateral hexagonal faces.It is also called an elongated dodecahedron and extended rhombic dodecahedron because it is related to the rhombic dodecahedron by expanding four rhombic faces of the rhombic dodecahedron into...
.
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
nth-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
nth-order Voronoi diagram from set
S, start with the (
n − 1)
th-order diagram and replace each cell generated by
X = {
x1,
x2, ...,
xn−1} 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 = {
p1,
p2, ...,
pn} the Farthest-Point Voronoi Diagram divides the plane into cells in which the same point of
P is the farthest point. Note that a point of
P has a cell in the Farthest-Point Voronoi diagram if and only if it is a vertex of the
convex hullIn mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of
P. Thus, let
H = {
h1,
h2, ...,
hk} be the convex hull of
P we define the Farthest-Point Voronoi diagram as the 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
hi if and only if
dist(q, h
i
) > dist(q, p
j
) for each
pj∈
S with
hi ≠
pj. Where
dist(p, q) is the
euclidean distanceIn mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
between two points
p and
q.
Generalizations and variations
As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean (such as the
MahalanobisIn statistics, Mahalanobis distance is a distance measure introduced by P. C. Mahalanobis in 1936. It is based on correlations between variables by which different patterns can be identified and analyzed. It gauges similarity of an unknown sample set to a known one. It differs from Euclidean...
or Manhattan) distances. 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 2-dimensional case.
A
weighted Voronoi diagramIn mathematics, a weighted Voronoi diagram in n dimensions is a Voronoi diagram for which the Voronoi cells are defined in terms of a distance defined by some common metrics modified by weights assigned to generator points....
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
metricMetric may refer to:* the metric system of measurement** International System of Units, or Système International , the modern form of the metric system** Metric ton, a measurement of mass equal to 1,000 kg...
, in this case some of the Voronoi cells may be empty.
The Voronoi diagram of
n points in
d-dimensional space requires
storage space. Therefore, Voronoi diagrams are often not feasible for
d > 2. An alternative is to use approximate Voronoi diagrams, where the Voronoi cells have a fuzzy boundary, which can be approximated.
Voronoi diagram are also related to other geometric structures such as the
medial axisThe 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 by Blum as a tool for biological shape recognition....
(which has found applications in image segmentation,
optical character recognitionOptical character recognition, usually abbreviated to OCR, is the mechanical or electronic translation of scanned images of handwritten, typewritten or printed text into machine-encoded text. It is widely used to convert books and documents into electronic files, to computerize a record-keeping...
and other computational applications) and the
straight skeletonIn 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 polygon may involve parabolic curves.Straight skeletons...
.
Applications
- One of the early applications of Voronoi diagrams was by John Snow
John Snow was an English physician and a leader in the adoption of anaesthesia and medical hygiene. He is considered to be one of the fathers of epidemiology, because of his work in tracing the source of a cholera outbreak in Soho, England, in 1854.-Early life and education:Snow was born 15 March...
to study the epidemiologyEpidemiology is the study of health-event, health-characteristic, or health-determinant patterns in a population. It is the cornerstone method of public health research, and helps inform policy decisions and evidence-based medicine by identifying risk factors for disease and targets for preventive...
of the 1854 Broad Street cholera outbreakThe Broad Street cholera outbreak was a severe outbreak of cholera that occurred near Broad Street in Soho district of London, England in 1854...
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
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 , motion planning, and computer aided design ....
data structure can be built on top of the Voronoi diagram in order to answer nearest neighborNearest neighbor may refer to:* Nearest neighbor search in pattern recognition and in computational geometry* Nearest-neighbor interpolation for interpolating data* Nearest neighbor graph in geometry...
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 databaseA database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...
. A large application is vector quantizationVector quantization is a classical quantization technique from signal processing which allows the modeling of probability density functions by the distribution of prototype vectors. It was originally used for data compression. It works by dividing a large set of points into groups having...
, commonly used in data compressionIn computer science and information theory, data compression, source coding or bit-rate reduction is the process of encoding information using fewer bits than the original representation would use....
.
- With a given Voronoi diagram, one can also 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:...
amongst 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 — sharpness of handwriting patterns*Roundness — measure of sharpness of a particle's corners*Roundness — roundness of clastic particles...
of a set of points.
- The Voronoi diagram is useful in polymer physics. It can be used to represent free volume of the polymer.
- It is also used in derivations of the capacity of a wireless network
Wireless network refers to any type of computer network that is not connected by cables of any kind. It is a method by which homes, telecommunications networks and enterprise installations avoid the costly process of introducing cables into a building, or as a connection between various equipment...
.
- 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.
- 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.
- Voronoi diagrams are also used in computer graphics to procedurally generate some kinds 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
Computational chemistry is a branch of chemistry that uses principles of computer science to assist in solving chemical problems. It uses the results of theoretical chemistry, incorporated into efficient computer programs, to calculate the structures and properties of molecules and solids...
, Voronoi cells defined by the positions of the nuclei in a molecule are used to compute atomic chargeA partial charge is a charge with an absolute value of less than one elementary charge unit .-Partial atomic charges:...
s. This is done using the Voronoi deformation densityVoronoi Deformation Density is a method employed in computational chemistry to compute the atomic charge distribution of a molecule in order to provide information about its chemical properties. The method is based on the partitioning of space into non-overlapping atomic areas modelled as Voronoi...
method.
- In materials science, polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations.
- Voronoi Polygons have been used in mining
Mining is the extraction of valuable minerals or other geological materials from the earth, from an ore body, vein or seam. The term also includes the removal of soil. Materials recovered by mining include base metals, precious metals, iron, uranium, coal, diamonds, limestone, oil shale, rock...
to estimate the reserves of valuable materials, minerals or other resources. Exploratory drillholes are used as the set of points in the Voronoi polygons.
See also
Algorithms
- Bowyer–Watson algorithm -- an algorithm for generating a Voronoi diagram in any number of dimensions.
- 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 time and O space...
-- an OIn mathematics, big O notation is used to describe the limiting behavior of a function when the argument tends towards a particular value or infinity, usually in terms of simpler functions. It is a member of a larger family of notations that is called Landau notation, Bachmann-Landau notation, or...
(n log(n)) algorithm for generating a Voronoi diagram from a set of points in a plane.
- Lloyd's algorithm
In computer science and electrical engineering, Lloyd's algorithm, also known as Voronoi iteration or relaxation, is an algorithm for grouping data points into a given number of categories, used for k-means clustering....
Related subjects
- Centroidal Voronoi tessellation
In geometry, a centroidal Voronoi tessellation is a special type of Voronoi tessellation or Voronoi diagrams. A Voronoi tessellation is called centroidal when the generating point of each Voronoi cell is also its mean . It can be viewed as an optimal partition corresponding to an optimal...
- Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
- Delaunay triangulation
In mathematics and computational geometry, a Delaunay triangulation for a set P of points in a plane is a triangulation DT such that no point in P is inside the circumcircle of any triangle in DT. Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the...
- Mathematical diagram
Mathematical diagrams are diagrams in the field of mathematics, and diagrams using mathematics such as charts and graphs, that are mainly designed to convey mathematical relationships, for example, comparisons over time.- Argand diagram :...
- Nearest neighbor search
Nearest neighbor search , also known as proximity search, similarity search or closest point search, is an optimization problem for finding closest points in metric spaces. The problem is: given a set S of points in a metric space M and a query point q ∈ M, find the closest point in S to q...
- Nearest-neighbor interpolation
- Pole
Given a point set and the corresponding Voronoi Diagram, then for each cell at most two poles are defined, namely the positive and negative poles.-Definition:...
External links
- Real time interactive Voronoi / Delaunay diagrams with draggable points, Java 1.0.2, 1996-1997
- Real time interactive Voronoi and Delaunay diagrams with source code
- Demo for various metrics
- Mathworld on Voronoi diagrams
- Qhull for computing the Voronoi diagram in 2-d, 3-d, etc.
- Voronoi Diagrams: Applications from Archaeology to Zoology
- Voronoi Diagrams in CGAL
The Computational Geometry Algorithms Library is a software library that aims to provide easy access to efficient and reliable algorithms in computational geometry. While primarily written in C++, Python and Scilab bindings are also available....
, the Computational Geometry Algorithms Library
- Voronoi Web Site : using Voronoi diagrams for spatial analysis
- More discussions and picture gallery on centroidal Voronoi tessellations
- Voronoi Diagrams by Ed Pegg, Jr.
Ed Pegg, Jr. is an expert on mathematical puzzles and is a self-described recreational mathematician. He creates puzzles for the Mathematical Association of America online at Ed Pegg, Jr.'s Math Games. His puzzles have also been used by Will Shortz on the puzzle segment of NPR's Weekend Edition...
, Jeff Bryant, and Theodore GrayTheodore W. Gray is one of the founders of Wolfram Research and is currently Wolfram's Director of User Interface Technology.He is a prominent element collector and created a wooden periodic table with compartments for samples of each of the elements...
, Wolfram Demonstrations ProjectThe Wolfram Demonstrations Project is hosted by Wolfram Research, whose stated goal is to bring computational exploration to the widest possible audience. It consists of an organized, open-source collection of small interactive programs called Demonstrations, which are meant to visually and...
.
- Nice explanation of voronoi diagram and visual implementation of fortune's algorithm