Voronoi diagram

Last updated
20 points and their Voronoi cells (larger version below) Euclidean Voronoi diagram.svg
20 points and their Voronoi cells (larger version below)

In mathematics, a Voronoi diagram is a partition of a plane 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, called Voronoi cells, 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 its Delaunay triangulation.

Contents

The Voronoi diagram is named after Georgy Voronoy, and is also called a Voronoi tessellation, a Voronoi decomposition, a Voronoi partition, or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet). Voronoi cells are also known as Thiessen polygons. [1] [2] [3] Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology, but also in visual art. [4] [5]

The simplest case

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 Euclidean plane whose distance to pk is less than or equal to its distance to any other pk. Each such cell is obtained from the intersection of half-spaces, and hence it is a (convex) polyhedron. [6] The line 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 be a metric space with distance function . Let be a set of indices and let be a tuple (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 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 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, 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, [7] "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:

or the Manhattan distance:

.

The corresponding Voronoi diagrams look different for different distance metrics.

Voronoi diagrams of 20 points under two different metrics

Properties

History and research

Informal use of Voronoi diagrams can be traced back to Descartes in 1644. Peter Gustav Lejeune Dirichlet used two-dimensional and three-dimensional Voronoi diagrams in his study of quadratic forms in 1850. British physician John Snow used a Voronoi-like diagram in 1854 to illustrate how the majority of people who died in the Broad Street cholera outbreak lived closer to the infected Broad Street pump 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. [10] Voronoi diagrams that are used in geophysics and meteorology 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

This is a slice of the Voronoi diagram of a random set of points in a 3D box. In general, a cross section of a 3D Voronoi tessellation is not a 2D Voronoi tessellation itself. (The cells are all convex polyhedra.) Coloured Voronoi 3D slice.svg
This is a slice of the Voronoi diagram of a random set of points in a 3D box. In general, a cross section of a 3D Voronoi tessellation is not a 2D Voronoi tessellation itself. (The cells are all convex polyhedra.)

Voronoi tessellations of regular lattices of points in two or three dimensions give rise to many familiar tessellations.

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. 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 of P. Let H = {h1, h2, ..., hk} 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 hi if and only if d(q, hi) > d(q, pj) for each pj  S with hipj, where d(p, q) is the Euclidean distance between two points p and q. [11] [12]

The boundaries of the cells in the farthest-point Voronoi diagram have the structure of a topological tree, with infinite rays as its leaves. Every finite tree is isomorphic to the tree formed in this way from a farthest-point Voronoi diagram. [13]

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. 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.

Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells. Approximate Voronoi Diagram.svg
Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.

A weighted Voronoi diagram 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, in this case some of the Voronoi cells may be empty. A power diagram is a type of Voronoi diagram defined from a set of circles using the power distance; 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 from the circle's center. [14]

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. [15]

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. [16] 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. [17]

Applications

Humanities

Natural sciences

A Voronoi tessellation emerges by radial growth from seeds outward. Voronoi growth euclidean.gif
A Voronoi tessellation emerges by radial growth from seeds outward.

Health

Engineering

Geometry

Informatics

Civics and planning

Bakery

Algorithms

Several efficient algorithms are known for constructing Voronoi diagrams, either directly (as the diagram itself) or indirectly by starting with a Delaunay triangulation and then obtaining its dual. Direct algorithms include Fortune's algorithm, an O(n log(n)) algorithm for generating a Voronoi diagram from a set of points in a plane. Bowyer–Watson algorithm, an O(n log(n)) to O(n2) 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. [39] [40]

Lloyd's algorithm and its generalization via the Linde–Buzo–Gray algorithm (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

Notes

  1. Burrough, Peter A.; McDonnell, Rachael; McDonnell, Rachael A.; Lloyd, Christopher D. (2015). "8.11 Nearest neighbours: Thiessen (Dirichlet/Voroni) polygons". Principles of Geographical Information Systems. Oxford University Press. pp. 160–. ISBN   978-0-19-874284-5.
  2. Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rhind, David W. (2005). "14.4.4.1 Thiessen polygons". Geographic Information Systems and Science. Wiley. pp. 333–. ISBN   978-0-470-87001-3.
  3. Sen, Zekai (2016). "2.8.1 Delaney, Varoni, and Thiessen Polygons". Spatial Modeling Principles in Earth Sciences. Springer. pp. 57–. ISBN   978-3-319-41758-5.
  4. 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. S2CID   4613674.
  5. Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000). Spatial Tessellations – Concepts and Applications of Voronoi Diagrams (2nd ed.). John Wiley. ISBN   978-0-471-98635-5.
  6. Boyd, Stephen; Vandenberghe, Lieven (2004). Convex Optimization. Exercise 2.9: Cambridge University Press. p. 60.CS1 maint: location (link)
  7. Tran, Q. T.; Tainar, D.; Safar, M. (2009). Transactions on Large-Scale Data- and Knowledge-Centered Systems. p. 357. ISBN   9783642037214.
  8. Reem 2009.
  9. Reem 2011.
  10. Voronoï 1908a and Voronoï 1908b.
  11. 1 2 de Berg, Mark; van Kreveld, Marc; Overmars, Mark; Schwarzkopf, Otfried (2008). Computational Geometry (Third ed.). Springer-Verlag. ISBN   978-3-540-77974-2. 7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
  12. Skyum, Sven (18 February 1991). "A simple algorithm for computing the smallest enclosing circle". Information Processing Letters. 37 (3): 121–125. doi:10.1016/0020-0190(91)90030-L., contains a simple algorithm to compute the farthest-point Voronoi diagram.
  13. Biedl, Therese; Grimm, Carsten; Palios, Leonidas; Shewchuk, Jonathan; Verdonschot, Sander (2016). "Realizing farthest-point Voronoi diagrams". Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016).
  14. Edelsbrunner, Herbert (2012) [1987]. "13.6 Power Diagrams". Algorithms in Combinatorial Geometry. EATCS Monographs on Theoretical Computer Science. 10. Springer-Verlag. pp. 327–328. ISBN   9783642615689..
  15. Sunil Arya, Sunil; Malamatos, Theocharis; Mount, David M. (2002). "Space-efficient approximate Voronoi diagrams". Proceedings of the thiry-fourth annual ACM symposium on Theory of computing. pp. 721–730. doi:10.1145/509907.510011. ISBN   1581134959. S2CID   1727373.
  16. Geraerts, Roland (2010), Planning Short Paths with Clearance using Explicit Corridors (PDF), International Conference on Robotics and Automation, IEEE, pp. 1997–2004.
  17. van Toll, Wouter G.; Cook IV, Atlas F.; van Kreveld, Marc J.; Geraerts, Roland (2018), The Medial Axis of a Multi-Layered Environment and its Application as a Navigation Mesh (PDF), ACM Transactions on Spatial Algorithms and Systems, pp. 2:1–2:34.
  18. Hölscher, Tonio; Krömker, Susanne; Mara, Hubert (2020), "Der Kopf Sabouroff in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung", Gedenkschrift für Georgios Despinis (in German), Athens, Greece: Benaki Museum
  19. Voronoi Cells & Geodesic Distances - Sabouroff head on YouTube. Analysis using the GigaMesh Software Framework as described by Hölscher et al. cf. doi:10.11588/heidok.00027985.
  20. Bock, Martin; Tyagi, Amit Kumar; Kreft, Jan-Ulrich; Alt, Wolfgang (2009). "Generalized Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics". Bulletin of Mathematical Biology. 72 (7): 1696–1731. arXiv: 0901.4469v1 . Bibcode:2009arXiv0901.4469B. doi:10.1007/s11538-009-9498-3. PMID   20082148. S2CID   16074264.
  21. Hui Li (2012). Baskurt, Atilla M; Sitnik, Robert (eds.). "Spatial Modeling of Bone Microarchitecture". Three-Dimensional Image Processing (3Dip) and Applications Ii. 8290: 82900P. Bibcode:2012SPIE.8290E..0PL. doi:10.1117/12.907371. S2CID   1505014.
  22. 1 2 Sanchez-Gutierrez, D.; Tozluoglu, M.; Barry, J. D.; Pascual, A.; Mao, Y.; Escudero, L. M. (2016-01-04). "Fundamental physical cellular constraints drive self-organization of tissues". The EMBO Journal. 35 (1): 77–88. doi:10.15252/embj.201592374. PMC   4718000 . PMID   26598531.
  23. Feinstein, Joseph; Shi, Wentao; Ramanujam, J.; Brylinski, Michal (2021), Ballante, Flavio (ed.), "Bionoi: A Voronoi Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications", Protein-Ligand Interactions and Drug Design, Methods in Molecular Biology, New York, NY: Springer US, 2266, pp. 299–312, doi:10.1007/978-1-0716-1209-5_17, ISBN   978-1-0716-1209-5, PMID   33759134 , retrieved 2021-04-23
  24. Springel, Volker (2010). "E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh". MNRAS. 401 (2): 791–851. arXiv: 0901.4107 . Bibcode:2010MNRAS.401..791S. doi:10.1111/j.1365-2966.2009.15715.x. S2CID   119241866.
  25. Kasim, Muhammad Firmansyah (2017-01-01). "Quantitative shadowgraphy and proton radiography for large intensity modulations". Physical Review E. 95 (2): 023306. arXiv: 1607.04179 . Bibcode:2017PhRvE..95b3306K. doi:10.1103/PhysRevE.95.023306. PMID   28297858. S2CID   13326345.
  26. Steven Johnson (19 October 2006). The Ghost Map: The Story of London's Most Terrifying Epidemic — and How It Changed Science, Cities, and the Modern World. Penguin Publishing Group. p. 187. ISBN   978-1-101-15853-1 . Retrieved 16 October 2017.
  27. Mulheran, P. A.; Blackman, J. A. (1996). "Capture zones and scaling in homogeneous thin-film growth". Physical Review B. 53 (15): 10261–7. Bibcode:1996PhRvB..5310261M. doi:10.1103/PhysRevB.53.10261. PMID   9982595.
  28. Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014). "Scaling and Exponent Equalities in Island Nucleation: Novel Results and Application to Organic Films". The Journal of Physical Chemistry Letters. 5 (6): 995–8. doi:10.1021/jz500282t. PMC   3962253 . PMID   24660052.
  29. Fanfoni, M.; Placidi, E.; Arciprete, F.; Orsini, E.; Patella, F.; Balzarotti, A. (2007). "Sudden nucleation versus scale invariance of InAs quantum dots on GaAs". Physical Review B. 75 (24): 245312. Bibcode:2007PhRvB..75x5312F. doi:10.1103/PhysRevB.75.245312. ISSN   1098-0121.
  30. Miyamoto, Satoru; Moutanabbir, Oussama; Haller, Eugene E.; Itoh, Kohei M. (2009). "Spatial correlation of self-assembled isotopically pure Ge/Si(001) nanoislands". Physical Review B. 79 (165415): 165415. Bibcode:2009PhRvB..79p5415M. doi:10.1103/PhysRevB.79.165415. ISSN   1098-0121. S2CID   13719907.
  31. "GOLD COAST CULTURAL PRECINCT". ARM Architecture.
  32. Lopez, C.; Zhao, C.-L.; Magniol, S; Chiabaut, N; Leclercq, L (28 February 2019). "Microscopic Simulation of Cruising for Parking of Trucks as a Measure to Manage Freight Loading Zone". Sustainability. 11 (5), 1276.
  33. Singh, K.; Sadeghi, F.; Correns, M.; Blass, T. (December 2019). "A microstructure based approach to model effects of surface roughness on tensile fatigue". International Journal of Fatigue. 129: 105229. doi:10.1016/j.ijfatigue.2019.105229.
  34. Cortes, J.; Martinez, S.; Karatas, T.; Bullo, F. (April 2004). "Coverage control for mobile sensing networks". IEEE Transactions on Robotics and Automation. 20 (2): 243–255. doi:10.1109/TRA.2004.824698. ISSN   2374-958X.
  35. Teruel, Enrique; Aragues, Rosario; López-Nicolás, Gonzalo (April 2021). "A Practical Method to Cover Evenly a Dynamic Region With a Swarm". IEEE Robotics and Automation Letters. 6 (2): 1359–1366. doi:10.1109/LRA.2021.3057568. ISSN   2377-3766.
  36. Mitchell, Tom M. (1997). Machine Learning (International ed.). McGraw-Hill. p.  233. ISBN   978-0-07-042807-2.
  37. "User Interface Algorithms".
  38. "School zones". Victorian Government Department of Education and Training. Retrieved 2020-08-24.
  39. https://www.comp.nus.edu.sg/~tants/jfa/i3d06.pdf
  40. https://www.shadertoy.com/view/4syGWK

Related Research Articles

Delaunay triangulation Triangulation method named after Boris Delaunay

In mathematics and computational geometry, a Delaunay 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 of any triangle in DT(P). Delaunay triangulations maximize the minimum angle of all the angles of the triangles in the triangulation; they tend to avoid sliver triangles. The triangulation is named after Boris Delaunay for his work on this topic from 1934.

Convex hull The smallest convex set containing a given set

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, or equivalently as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

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 geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with a history stretching back to antiquity.

Discrete geometry Branch of geometry that studies combinatorial properties and constructive methods

Discrete geometry and combinatorial geometry are branches of geometry that study combinatorial properties and constructive methods of discrete geometric objects. Most questions in discrete geometry involve finite or discrete sets of basic geometric objects, such as points, lines, planes, circles, spheres, polygons, and so forth. The subject focuses on the combinatorial properties of these objects, such as how they intersect one another, or how they may be arranged to cover a larger object.

Wigner–Seitz cell Primitive cell of crystal lattices with Voronoi decomposition applied

The Wigner–Seitz cell, named after Eugene Wigner and Frederick Seitz, is a primitive cell which has been constructed by applying Voronoi decomposition to a crystal lattice. It is used in the study of crystalline materials in solid-state physics.

k-means clustering is a method of vector quantization, originally from signal processing, that aims to partition n observations into k clusters in which each observation belongs to the cluster with the nearest mean, serving as a prototype of the cluster. This results in a partitioning of the data space into Voronoi cells. k-means clustering minimizes within-cluster variances, but not regular Euclidean distances, which would be the more difficult Weber problem: the mean optimizes squared errors, whereas only the geometric median minimizes Euclidean distances. For instance, better Euclidean solutions can be found using k-medians and k-medoids.

Medoids are representative objects of a data set or a cluster within a data set whose average dissimilarity to all the objects in the cluster is minimal. Medoids are similar in concept to means or centroids, but medoids are always restricted to be members of the data set. Medoids are most commonly used on data when a mean or centroid cannot be defined, such as graphs. They are also used in contexts where the centroid is not representative of the dataset like in images and 3-D trajectories and gene expression. These are also of interest while wanting to find a representative using some distance other than squared euclidean distance.

Lloyds 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 these subsets into well-shaped and uniformly sized convex cells. Like the closely related k-means clustering algorithm, it repeatedly finds the centroid of each set in the partition and then re-partitions the input according to which of these centroids is closest. In this setting, the mean operation is an integral over a region of space, and the nearest centroid operation results in Voronoi diagrams.

Tetrahedral-octahedral honeycomb Quasiregular space-filling tesselation

The tetrahedral-octahedral honeycomb, alternated cubic honeycomb is a quasiregular space-filling tessellation in Euclidean 3-space. It is composed of alternating regular octahedra and tetrahedra in a ratio of 1:2.

Nearest neighbor search (NNS), as a form of proximity search, is the optimization problem of finding the point in a given set that is closest to a given point. Closeness is typically expressed in terms of a dissimilarity function: the less similar the objects, the larger the function values.

24-cell honeycomb

In four-dimensional Euclidean geometry, the 24-cell honeycomb, or icositetrachoric honeycomb is a regular space-filling tessellation of 4-dimensional Euclidean space by regular 24-cells. It can be represented by Schläfli symbol {3,4,3,3}.

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 the dual graph of the Delaunay triangulation.

Centroidal Voronoi tessellation Voronoi tessellation where the generating point of each Voronoi cell is also its centroid

In geometry, a centroidal Voronoi tessellation (CVT) is a special type of Voronoi tessellation in which the generating point of each Voronoi cell is also its centroid. It can be viewed as an optimal partition corresponding to an optimal distribution of generators. A number of algorithms can be used to generate centroidal Voronoi tessellations, including Lloyd's algorithm for K-means clustering or Quasi-Newton methods like BFGS.

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 Euclidean distance, or may be some other, special distance function. In weighted Voronoi diagrams, each site has a weight that influences the distance computation. The idea is that larger weights indicate more important sites, and such sites will get bigger Voronoi cells.

A zone diagram is a certain geometric object which a variation on the notion of Voronoi diagram. It was introduced by Tetsuo Asano, Jiri Matousek, and Takeshi Tokuyama in 2007.

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 a set of circles. The cell for a given circle C consists of all the points for which the power distance to C is smaller than the power distance to the other circles. The power diagram is a form of generalized Voronoi diagram, and coincides with the Voronoi diagram of the circle centers in the case that all the circles have equal radii.

Delone set

In the mathematical theory of metric spaces, ε-nets, ε-packings, ε-coverings, uniformly discrete sets, relatively dense sets, and Delone sets are several closely related definitions of well-spaced sets of points, and the packing radius and covering radius of these sets measure how well-spaced they are. These sets have applications in coding theory, approximation algorithms, and the theory of quasicrystals.

Farthest-first traversal Algorithm

In computational geometry, the farthest-first traversal of a bounded metric space is a sequence of points in the space, where the first point is selected arbitrarily and each successive point is as far as possible from the set of previously-selected points. The same concept can also be applied to a finite set of geometric points, by restricting the selected points to belong to the set or equivalently by considering the finite metric space generated by these points. For a finite metric space or finite set of geometric points, the resulting sequence forms a permutation of the points, known as the greedy permutation.

In geometry, a plesiohedron is a special kind of space-filling polyhedron, defined as the Voronoi cell of a symmetric Delone set. Three-dimensional Euclidean space can be completely filled by copies of any one of these shapes, with no overlaps. The resulting honeycomb will have symmetries that take any copy of the plesiohedron to any other copy.

References

Software

Voronoi diagrams require a computational step before showing the results. An efficient tool therefore would process the computation in real-time to show a direct result to the user. Many commercial and free applications exist. A particularly practical type of tools are the web-based ones. Web-based tools are easier to access and reference. Also, SVG being a natively supported format by the web, allows at the same time an efficient (GPU accelerated) rendering and is a standard format supported by multiple CAD tools (e.g. Autodesk Fusion360).

Although voronoi is a very old concept, the currently available tools do lack multiple mathematical functions that could add values to these programs.[ opinion ] Examples could be usage of a different cost distance than Euclidean, and mainly 3d voronoi algorithms. Although not being software tools themselves, the first reference explains the concept of 3d voronoi and the second is a 3d voronoi library.