In mathematics, a
Contents 1 The simplest case 2 Formal definition 3 Illustration 4 Properties 5 History and research 6 Examples 7 Higher-order Voronoi diagrams 7.1 Farthest-point Voronoi diagram 8 Generalizations and variations 9 Applications 9.1 Natural sciences 9.2 Health 9.3 Engineering 9.4 Geometry 9.5 Informatics 9.6 Civics and planning 10 Algorithms 11 See also 12 Notes 13 References 14 External links The simplest case[edit]
In the simplest 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 Rk consists of every point in the
X displaystyle scriptstyle X be a metric space with distance function d displaystyle scriptstyle d . Let K displaystyle scriptstyle K be a set of indices and let ( P k ) k ∈ K displaystyle scriptstyle (P_ k )_ kin K be a tuple (ordered collection) of nonempty subsets (the sites) in the space X displaystyle scriptstyle X . The Voronoi cell, or Voronoi region, R k displaystyle scriptstyle R_ k , associated with the site P k displaystyle scriptstyle P_ k is the set of all points in X displaystyle scriptstyle X whose distance to P k displaystyle scriptstyle P_ k is not greater than their distance to the other sites P j displaystyle scriptstyle P_ j , where j displaystyle scriptstyle j is any index different from k displaystyle scriptstyle k . In other words, if d ( x , A ) = inf d ( x , a ) ∣ a ∈ A displaystyle scriptstyle d(x,,A);=;inf d(x,,a)mid a,in ,A denotes the distance between the point x displaystyle scriptstyle x and the subset A displaystyle scriptstyle A , then R k = x ∈ X ∣ d ( x , P k ) ≤ d ( x , P j ) for all j ≠ k displaystyle R_ k = xin Xmid d(x,P_ k )leq d(x,P_ j ); text for all ;jneq k The
( R k ) k ∈ K displaystyle scriptstyle (R_ k )_ kin 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 numbers and crystallography), but again, in many cases only finitely many sites are considered. In the particular case where the space is a finite-dimensional Euclidean space, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex 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. In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon R k displaystyle scriptstyle R_ k is associated with a generator point P k displaystyle scriptstyle P_ k . Let X displaystyle scriptstyle X be the set of all points in the Euclidean space. Let P 1 displaystyle scriptstyle P_ 1 be a point that generates its Voronoi region R 1 displaystyle scriptstyle R_ 1 , P 2 displaystyle scriptstyle P_ 2 that generates R 2 displaystyle scriptstyle R_ 2 , and P 3 displaystyle scriptstyle P_ 3 that generates R 3 displaystyle scriptstyle R_ 3 , and so on. Then, as expressed by Tran et al[6] "all locations in the
Voronoi polygon are closer to the generator point of that polygon than
any other generator point in the
R k displaystyle scriptstyle R_ k of a given shop P k displaystyle scriptstyle P_ k 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: ℓ 2 = d [ ( a 1 , a 2 ) , ( b 1 , b 2 ) ] = ( a 1 − b 1 ) 2 + ( a 2 − b 2 ) 2 displaystyle ell _ 2 =dleft[left(a_ 1 ,a_ 2 right),left(b_ 1 ,b_ 2 right)right]= sqrt left(a_ 1 -b_ 1 right)^ 2 +left(a_ 2 -b_ 2 right)^ 2 or the Manhattan distance: d [ ( a 1 , a 2 ) , ( b 1 , b 2 ) ] =
a 1 − b 1
+
a 2 − b 2
displaystyle dleft[left(a_ 1 ,a_ 2 right),left(b_ 1 ,b_ 2 right)right]=lefta_ 1 -b_ 1 right+lefta_ 2 -b_ 2 right . The corresponding Voronoi diagrams look different for different distance metrics. Voronoi diagrams of 20 points under two different metrics Euclidean distance Manhattan distance Properties[edit] The dual graph for a
History and research[edit]
Informal use of Voronoi diagrams can be traced back to
This is a slice of the
Voronoi tessellations of regular lattices 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 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. A hexagonal close-packed lattice gives a tessellation of space with trapezo-rhombic dodecahedra. A face-centred cubic lattice gives a tessellation of space with rhombic dodecahedra. A body-centred cubic lattice gives a tessellation of space with truncated octahedra. Parallel planes with regular triangular lattices aligned with each other's centers give the hexagonal prismatic honeycomb. 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[edit]
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
Approximate
A weighted
O ( n ⌈ 1 2 d ⌉ ) displaystyle scriptstyle Oleft(n^ leftlceil frac 1 2 drightrceil right) storage space.[clarification needed] Therefore, Voronoi diagrams are often not feasible for d > 2.[clarification needed] An alternative is to use approximate Voronoi diagrams, where the Voronoi cells have a fuzzy boundary, which can be approximated.[13] Voronoi diagrams are also related to other geometric structures such as the medial axis (which has found applications in image segmentation, optical character recognition, and other computational applications), straight skeleton, and zone diagrams. Besides points, such diagrams use lines and polygons as seeds. By augmenting the diagram with line segments that connect to nearest points on the seeds, a planar subdivision of the environment is obtained.[14] This structure can be used as a navigation mesh for path-finding through large spaces. The navigation mesh has been generalized to support 3D multi-layered environments, such as an airport or a multi-storey building.[15] Applications[edit] Natural sciences[edit] A Voronoi tessellation emerges by radial growth from seeds outward. In biology, Voronoi diagrams are used to model a number of different
biological structures, including cells[16] and bone
microarchitecture.[17] Indeed, Voronoi tessellations work as a
geometrical tool to understand the physical constraints that drive the
organization of biological tissues.[18]
In hydrology, Voronoi diagrams are used to calculate the rainfall of
an area, based on a series of point measurements. In this usage, they
are generally referred to as Thiessen polygons.
In ecology, Voronoi diagrams are used to study the growth patterns of
forests and forest canopies, and may also be helpful in developing
predictive models for forest fires.
In computational chemistry, Voronoi cells defined by the positions of
the nuclei in a molecule are used to compute atomic charges. This is
done using the
Health[edit] In medical diagnosis, models of muscle tissue, based on Voronoi diagrams, can be used to detect neuromuscular diseases.[18] John Snow's original diagram In epidemiology, 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 to study the 1854 Broad Street cholera outbreak 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 most deaths due to the outbreak.[21] Engineering[edit] 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 solid
state physics, the
Geometry[edit] A point location data structure can be built on top of the Voronoi diagram in order to answer nearest neighbor queries, where one wants to find the object that is closest to a given query point. Nearest neighbor queries have numerous applications. For example, one might want to find the nearest hospital, or the most similar object in a database. A large application is vector quantization, commonly used in data compression. In geometry, Voronoi diagrams can be used to find the largest empty circle amid a set of points, and in an enclosing polygon; e.g. to build a new supermarket as far as possible from all the existing ones, lying in a certain city. Voronoi diagrams together with farthest-point Voronoi diagrams are used for efficient algorithms to compute the roundness of a set of points.[9] The Voronoi approach is also put to good use in the evaluation of circularity/roundness while assessing the dataset from a coordinate-measuring machine. Informatics[edit] In networking, Voronoi diagrams can be used in derivations of the capacity of a wireless network. In computer graphics, 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, 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, Voronoi diagrams are used to do 1-NN classifications.[23] In user interface development, Voronoi patterns can be used to compute the best hover state for a given point.[24] Civics and planning[edit] In Victoria, Australia, government schools typically admit eligible students to the nearest primary school or high school to where they live.[25] Students and parents can see which school "catchment zone" they live in by using this Voronoi representation. Algorithms[edit] Direct algorithms: Fortune's algorithm, an O(n log(n)) algorithm for generating a Voronoi
diagram from a set of points in a plane.
Starting with a
Bowyer–Watson algorithm, an O(n log(n)) to O(n2) algorithm for
generating a
See also[edit] Centroidal Voronoi tessellation Computational geometry Delaunay triangulation Mathematical diagram Natural neighbor interpolation Nearest neighbor search Nearest-neighbor interpolation Voronoi pole Power diagram Map segmentation Notes[edit] ^ Aurenhammer, Franz (1991). "Voronoi Diagrams – A Survey of a
Fundamental Geometric Data Structure". ACM Computing Surveys. 23 (3):
345–405. doi:10.1145/116873.116880.
^ Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok
(2000). Spatial Tessellations – Concepts and Applications of Voronoi
Diagrams (2nd ed.). John Wiley. ISBN 0-471-98635-6.
^ Principles of Geographical Information Systems, By Peter A.
Burrough, Rachael McDonnell, Rachael A. McDonnell, Christopher D.
Lloyd [1]
^ Geographic Information Systems and Science, By Paul Longley
^ Spatial Modeling Principles in Earth Sciences, Zekai Sen
^ Tran, Q. T.; Tainar, D.; Safar, M. (2009). Transactions on
Large-Scale Data- and Knowledge-Centered Systems. p. 357.
ISBN 9783642037214.
^ Reem, Daniel (2009). "An algorithm for computing Voronoi diagrams of
general generators in general normed spaces". Proceedings of the sixth
International Symposium on Voronoi Diagrams in science and engineering
(ISVD 2009): 144–152. doi:10.1109/ISVD.2009.23.
^ Reem, Daniel (2011). "The geometric stability of Voronoi diagrams
with respect to small changes of the sites". Proceedings of the 27th
Annual ACM Symposium on Computational
References[edit] Dirichlet, G. Lejeune (1850). "Über die Reduktion der positiven
quadratischen Formen mit drei unbestimmten ganzen Zahlen". Journal
für die Reine und Angewandte Mathematik. 40: 209–227.
Voronoi, Georgy (1908). "Nouvelles applications des paramètres
continus à la théorie des formes quadratiques". Journal für die
Reine und Angewandte Mathematik. 1908 (133): 97–178.
doi:10.1515/crll.1908.133.97.
Atsuyuki Okabe, Barry Boots,
Daniel Reem (2011). The geometric stability of Voronoi diagrams with
respect to small changes of the sites. Full version: arXiv 1103.4125
(2011), Extended abstract: in Proceedings of the 27th Annual ACM
Symposium on Computational
External links[edit] Wikimedia Commons has media related to Voronoi diagrams. Real time interactive Voronoi and Delaunay diagrams with source code
Demo for various metrics
Mathworld on Voronoi diagrams
Voronoi Diagrams: Applications from Archaeology to Zoology
Voronoi Diagrams in CGAL, the Computational
v t e Tessellation Periodic Pythagorean Rhombille Schwarz triangle Rectangle Domino
Coloring Convex Kisrhombille Wallpaper group Wythoff Aperiodic Ammann–Beenker Aperiodic set of prototiles List Einstein problem Socolar–Taylor Gilbert
Penrose
Pentagonal
Pinwheel
Quaquaversal
Sphinx Truchet Other Anisohedral & Isohedral Architectonic & catoptric Circle Limit III Computer graphics Honeycomb Isotoxal List Packing Problems Domino Wang Heesch's Squaring Prototile Conway criterion Girih Regular Division of the Plane Regular grid Substitution Voronoi Voderberg By vertex type Spherical 2n 33.n V33.n 42.n V42.n Regular 2∞ 36 44 63 Semi- regular 32.4.3.4 V32.4.3.4 33.42 33.∞ 34.6 V34.6 3.4.6.4 (3.6)2 3.122 42.∞ 4.6.12 4.82 Hyper- bolic 32.4.3.5 32.4.3.6 32.4.3.7 32.4.3.8 32.4.3.∞ 32.5.3.5 32.5.3.6 32.6.3.6 32.6.3.8 32.7.3.7 32.8.3.8 33.4.3.4 32.∞.3.∞ 34.7 34.8 34.∞ 35.4 37 38 3∞ (3.4)3 (3.4)4 3.4.62.4 3.4.7.4 3.4.8.4 3.4.∞.4 3.6.4.6 (3.7)2 (3.8)2 3.142 3.162 (3.∞)2 3.∞2 42.5.4 42.6.4 42.7.4 42.8.4 42.∞.4 45 46 47 48 4∞ (4.5)2 (4.6)2 4.6.12 4.6.14 V4.6.14 4.6.16 V4.6.16 4.6.∞ (4.7)2 (4.8)2 4.8.10 V4.8.10 4.8.12 4.8.14 4.8.16 4.8.∞ 4.102 4.10.12 4.122 4.12.16 4.142 4.162 4.∞2 (4.∞)2 54 55 56 5∞ 5.4.6.4 (5.6)2 5.82 5.102 5.122 (5.∞)2 64 65 66 68 6.4.8.4 (6.8)2 6.82 6.102 6.122 6.162 73 74 77 7.62 7.82 7.142 83 84 86 88 812 8.62 8.162 ∞3 ∞4 ∞5 ∞∞ ∞.62 ∞.82 Authority control LCCN: sh88006450 GND: 4226013-9 SUDOC: 030005558 BNF: |