3235:
3247:
3211:
5452:
3223:
1863:
1849:
2411:
1931:, 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.
1992:
20:
2737:
3192:), 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
5459:
2569:
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
1383:
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
1983:, who used them to estimate rainfall from scattered measurements in 1911. 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).
1109:. 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
4416:
Löbl, Matthias C.; Zhai, Liang; Jahn, Jan-Philipp; Ritzmann, Julian; Huo, Yongheng; Wieck, Andreas D.; Schmidt, Oliver G.; Ludwig, Arne; Rastelli, Armando; Warburton, Richard J. (2019-10-03). "Correlations between optical properties and
Voronoi-cell area of quantum dots".
1131:
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.
3544:"Mathematical Structures: Spatial Tessellations . Concepts and Applications of Voronoi Diagrams. Atsuyuki Okabe, Barry Boots, and Kokichi Sugihara. Wiley, New York, 1992. xii, 532 pp., illus. $ 89.95. Wiley Series in Probability and Mathematical Statistics"
2422:
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
2011:
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
1648:
2532:
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
2407:. 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.
1055:
2986:
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
4010:
Feinstein, Joseph; Shi, Wentao; Ramanujam, J.; Brylinski, Michal (2021). "Bionoi: A Voronoi
Diagram-Based Representation of Ligand-Binding Sites in Proteins for Machine Learning Applications". In Ballante, Flavio (ed.).
3107:, 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.
1829:
2867:
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.
2677:
2016:
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
1924:
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.
896:
2808:, 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
3234:
3068:, 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).
2946:, 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.
2530:
169:
3246:
943:
3029:
2764:, 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.
2793:
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
1107:
621:
5181:"Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Premier mémoire. Sur quelques propriétés des formes quadratiques positives parfaites"
4740:
1451:
434:
3210:
3082:
In global scene reconstruction, including with random sensor sites and unsteady wake flow, geophysical data, and 3D turbulence data, Voronoi tesselations are used with
2705:
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
2601:
1375:, "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".
4562:
4365:
Miyamoto, Satoru; Moutanabbir, Oussama; Haller, Eugene E.; Itoh, Kohei M. (2009). "Spatial correlation of self-assembled isotopically pure Ge/Si(001) nanoislands".
1436:
1409:
461:
389:
362:
335:
308:
281:
254:
227:
200:
4314:
Fanfoni, M.; Placidi, E.; Arciprete, F.; Orsini, E.; Patella, F.; Balzarotti, A. (2007). "Sudden nucleation versus scale invariance of InAs quantum dots on GaAs".
2771:, 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.
487:
3854:
Bock, Martin; Tyagi, Amit Kumar; Kreft, Jan-Ulrich; Alt, Wolfgang (2009). "Generalized
Voronoi Tessellation as a Model of Two-dimensional Cell Tissue Dynamics".
1369:
1342:
1315:
1288:
1261:
1234:
1187:
1160:
777:
750:
703:
676:
2480:
2460:
51:. 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
1207:
936:
916:
817:
797:
723:
649:
575:
555:
531:
3010:
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.
5217:"Nouvelles applications des paramètres continus à la théorie des formes quadratiques. Deuxième mémoire. Recherches sur les parallélloèdres primitifs"
2859:, Voronoi diagrams can be used to correlate sources of infections in epidemics. One of the early applications of Voronoi diagrams was implemented by
3174:) algorithm for generating a Delaunay triangulation in any number of dimensions, can be used in an indirect algorithm for the Voronoi diagram. The
3130:
Several efficient algorithms are known for constructing
Voronoi diagrams, either directly (as the diagram itself) or indirectly by starting with a
3028:
Zeroes of iterated derivatives of a rational function on the complex plane accumulate on the edges of the
Voronoi diagam of the set of the poles (
2757:
Indeed, Voronoi tessellations work as a geometrical tool to understand the physical constraints that drive the organization of biological tissues.
1663:
4768:
1995:
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 a
5368:
4696:
Pólya, G. On the zeros of the derivatives of a function and its analytic character. Bulletin of the AMS, Volume 49, Issue 3, 178-191, 1943.
1438:
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).
6392:
2606:
5657:
3121:
uses the mathematical principles of the Voronoi diagram to create silicone molds made with a 3D printer to shape her original cakes.
505:
of the diagram, where three or more of these boundaries meet, are the points that have three or more equally distant nearest sites.
5590:
2435:; 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
3222:
6456:
6397:
5612:
5346:
5319:
4478:
5078:
4996:
4962:
4723:
4199:
4127:
Kasim, Muhammad Firmansyah (2017-01-01). "Quantitative shadowgraphy and proton radiography for large intensity modulations".
4030:
3838:
3636:
3448:
3385:
3356:
3327:
2917:, Voronoi diagrams are superimposed on oceanic plotting charts to identify the nearest airfield for in-flight diversion (see
6207:
6042:
6441:
6357:
6332:
6322:
6292:
6247:
6197:
6177:
5992:
5877:
4839:
Proceedings of the 2006 Symposium on Interactive 3D Graphics, SI3D 2006, March 14-17, 2006, Redwood City, California, USA
2603:
touching station point is known as influence area of the station. The average precipitation is calculated by the formula
59:, consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is
4191:
The Ghost Map: The Story of London's Most Terrifying Epidemic — and How It Changed Science, Cities, and the Modern World
6367:
6362:
6302:
6297:
6252:
6202:
6187:
4904:
2864:
1953:
1948:
used two-dimensional and three-dimensional Voronoi diagrams in his study of quadratic forms in 1850. British physician
822:
6387:
6172:
5420:
5123:
5051:
4980:
4854:
3715:
3502:
3185:
2414:
Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.
2391:
as its leaves. Every finite tree is isomorphic to the tree formed in this way from a farthest-point Voronoi diagram.
6227:
6162:
6147:
5982:
5602:
5061:
Reem, Daniel (2009). "An algorithm for computing Voronoi diagrams of general generators in general normed spaces".
6431:
6327:
6287:
6242:
6182:
6167:
6157:
6132:
5493:
3193:
3178:
can generate approximate Voronoi diagrams in constant time and is suited for use on commodity graphics hardware.
1127:, each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are
5216:
5180:
3013:
Voronoi diagrams together with farthest-point Voronoi diagrams are used for efficient algorithms to compute the
6192:
6112:
5967:
5170:
5145:
5088:
Reem, Daniel (2011). "The Geometric Stability of Voronoi Diagrams with Respect to Small Changes of the Sites".
5006:
3752:
3284:
3279:
1945:
91:
6446:
6122:
6107:
6067:
5997:
5947:
5862:
5682:
2545:
2080:
2072:
2065:
4523:
2682:
6092:
6057:
6047:
5907:
5063:
Proceedings of the Sixth International Symposium on Voronoi Diagrams in Science and Engineering (ISVD 2009)
3479:
3076:
3057:, Voronoi diagrams are used to calculate 3D shattering / fracturing geometry patterns. It is also used to
3022:
2816:
2036:
125:
2888:, polycrystalline microstructures in metallic alloys are commonly represented using Voronoi tessellations.
2485:
501:, or line, consisting of all the points in the plane that are equidistant to their two nearest sites. The
6451:
6436:
6232:
6062:
6052:
6032:
6012:
5987:
5932:
5912:
5897:
5887:
5822:
5488:
3812:
3151:
2835:
2798:
2534:
2399:
As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean, such as the
1135:
In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon
3961:
Sanchez-Gutierrez, D.; Tozluoglu, M.; Barry, J. D.; Pascual, A.; Mao, Y.; Escudero, L. M. (2016-01-04).
6426:
6382:
6377:
6372:
6277:
6037:
6002:
5962:
5942:
5917:
5902:
5892:
5852:
5339:
3915:
Hui Li (2012). Baskurt, Atilla M; Sitnik, Robert (eds.). "Spatial Modeling of Bone Microarchitecture".
3808:
2929:
2436:
4505:"Microscopic Simulation of Cruising for Parking of Trucks as a Measure to Manage Freight Loading Zone"
4267:"Scaling and Exponent Equalities in Island Nucleation: Novel Results and Application to Organic Films"
4222:
Mulheran, P. A.; Blackman, J. A. (1996). "Capture zones and scaling in homogeneous thin-film growth".
2819:, the Voronoi tessellation of a set of points can be used to define the computational domains used in
6317:
6312:
6222:
6217:
6212:
6007:
5977:
5972:
5952:
5937:
5927:
5922:
5842:
5483:
5009:(1850). "Über die Reduktion der positiven quadratischen Formen mit drei unbestimmten ganzen Zahlen".
3710:. EATCS Monographs on Theoretical Computer Science. Vol. 10. Springer-Verlag. pp. 327–328.
1643:{\displaystyle \ell _{2}=d\left={\sqrt {\left(a_{1}-b_{1}\right)^{2}+\left(a_{2}-b_{2}\right)^{2}}}}
6352:
6347:
6342:
6272:
6267:
6262:
6257:
5957:
5837:
5832:
2852:, models of muscle tissue, based on Voronoi diagrams, can be used to detect neuromuscular diseases.
2419:
5451:
5320:
Demo program for SFTessellation algorithm, which creates Voronoi diagram using a Steppe Fire Model
4715:
3653:
Skyum, Sven (18 February 1991). "A simple algorithm for computing the smallest enclosing circle".
1066:
580:
6017:
5867:
5817:
5505:
4764:
4741:"A Novel Deep Learning Technique That Rebuilds Global Fields Without Using Organized Sensor Data"
3175:
2983:
2786:
3196:, where the sites have been moved to points that are also the geometric centers of their cells.
2891:
In island growth, the Voronoi diagram is used to estimate the growth rate of individual islands.
1979:
to analyse spatially distributed data are called Thiessen polygons after American meteorologist
1384:
considerations: they will go to the shop located nearest to them. In this case the Voronoi cell
402:
6137:
6127:
6097:
5779:
5394:
3274:
3264:
3135:
3131:
2032:
1928:
1899:
1892:
396:
64:
4189:
3344:
3315:
6237:
6142:
6102:
6087:
6082:
6077:
6072:
5827:
5617:
5332:
4070:"E pur si muove: Galilean-invariant cosmological hydrodynamical simulations on a moving mesh"
4017:. Methods in Molecular Biology. Vol. 2266. New York, NY: Springer US. pp. 299–312.
3373:
3314:
Burrough, Peter A.; McDonnell, Rachael; McDonnell, Rachael A.; Lloyd, Christopher D. (2015).
3058:
3017:
of a set of points. The Voronoi approach is also put to use in the evaluation of circularity/
2860:
2827:
2809:
2694:
2573:
2235:} the farthest-point Voronoi diagram divides the plane into cells in which the same point of
1952:
used a Voronoi-like diagram in 1854 to illustrate how the majority of people who died in the
1949:
392:
60:
4812:
4707:
3543:
3093:
development, Voronoi patterns can be used to compute the best hover state for a given point.
2749:, Voronoi diagrams are used to model a number of different biological structures, including
2720:, Voronoi cells are used to indicate a supposed linguistic continuity between survey points.
2118:
Although a normal Voronoi cell is defined as the set of points closest to a single point in
2064:
Parallel planes with regular triangular lattices aligned with each other's centers give the
6282:
6022:
5735:
5723:
5607:
5536:
5512:
5437:
5261:
5157:
5103:
4975:
Klein, Rolf (1988). "Abstract voronoi diagrams and their applications: Extended abstract".
4923:
4436:
4374:
4323:
4231:
4146:
4091:
3924:
3873:
3816:
3703:
3181:
3007:
2424:
2400:
2058:
2047:
2021:
1999:, a weighted form of a 2d Voronoi diagram, rather than being an unweighted Voronoi diagram.
1414:
1387:
439:
367:
340:
313:
286:
259:
232:
205:
178:
52:
4524:"A microstructure based approach to model effects of surface roughness on tensile fatigue"
2383:
The boundaries of the cells in the farthest-point Voronoi diagram have the structure of a
8:
6027:
5847:
5693:
5652:
5647:
5527:
3620:
2992:
2895:
2779:
1110:
1050:{\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}}
466:
102:. Voronoi diagrams have practical and theoretical applications in many fields, mainly in
5161:
5107:
4708:
4563:"Voronoi-visibility roadmap-based path planning algorithm for unmanned surface vehicles"
4440:
4378:
4327:
4235:
4150:
4095:
3928:
3877:
5812:
5581:
5379:
5239:
5203:
5141:
5129:
5093:
5026:
4679:
4632:
4585:
4543:
4460:
4426:
4398:
4347:
4291:
4266:
4170:
4136:
4109:
4081:
4044:
3987:
3962:
3940:
3897:
3863:
3758:
3473:
3421:
3189:
3018:
3014:
2965:
2465:
2445:
2404:
2369:
2054:
2043:
1980:
1868:
1854:
1654:
1442:
1347:
1320:
1293:
1266:
1239:
1212:
1165:
1138:
1121:
755:
728:
681:
654:
99:
40:
2727:, Voronoi diagrams have been used to study multi-dimensional, multi-party competition.
2243:
has a cell in the farthest-point Voronoi diagram if and only if it is a vertex of the
1909:
and a discrete set of points is given. Then two points of the set are adjacent on the
122:
In the simplest case, shown in the first picture, we are given a finite set of points
6307:
5857:
5784:
5627:
5410:
5292:
5243:
5207:
5119:
5074:
5047:
5030:
4992:
4958:
4950:
4900:
4888:
4850:
4719:
4683:
4671:
4624:
4547:
4464:
4452:
4390:
4351:
4339:
4296:
4247:
4195:
4162:
4113:
4104:
4069:
4048:
4036:
4026:
3992:
3889:
3834:
3748:
3711:
3685:
3666:
3632:
3571:
3563:
3498:
3444:
3401:
3381:
3352:
3323:
3054:
2954:
2950:
2899:
2885:
2849:
2724:
2549:
2388:
2013:
502:
47:
into regions close to each of a given set of objects. It can be classified also as a
5295:
5133:
4589:
4539:
4482:
4402:
4174:
3901:
3343:
Longley, Paul A.; Goodchild, Michael F.; Maguire, David J.; Rhind, David W. (2005).
6337:
6152:
6117:
5794:
5758:
5703:
5669:
5622:
5596:
5585:
5500:
5472:
5415:
5389:
5384:
5269:
5231:
5195:
5165:
5111:
5066:
5039:
5018:
4984:
4931:
4842:
4831:
4663:
4636:
4616:
4577:
4535:
4444:
4382:
4331:
4286:
4278:
4239:
4154:
4099:
4018:
3982:
3974:
3944:
3932:
3881:
3762:
3740:
3662:
3612:
3555:
3425:
3413:
3269:
3072:
3065:
3047:
3043:
2996:
2790:
2432:
1192:
921:
901:
802:
782:
708:
634:
560:
540:
516:
44:
4832:"Jump flooding in GPU with applications to Voronoi diagram and distance transform"
3559:
2205: − 1)-order Voronoi diagram is called a farthest-point Voronoi diagram.
1927:
Under relatively general conditions (the space is a possibly infinite-dimensional
1835:
The corresponding Voronoi diagrams look different for different distance metrics.
5522:
5432:
4813:"Architect turned cake-maker serves up mouth-watering geometric 3D-printed cakes"
4503:
Lopez, C.; Zhao, C.-L.; Magniol, S; Chiabaut, N; Leclercq, L (28 February 2019).
4022:
3690:
Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG 2016)
3628:
3404:(1991). "Voronoi Diagrams – A Survey of a Fundamental Geometric Data Structure".
2928:, Voronoi patterns were the basis for the winning entry for the redevelopment of
2878:
2754:
2126:
th-order Voronoi cell is defined as the set of points having a particular set of
2025:
2004:
1906:
1888:
1128:
1124:
1114:
172:
4448:
1441:
For most cities, the distance between points can be measured using the familiar
5635:
5548:
5517:
5406:
4651:
4604:
4504:
4386:
4335:
4158:
4012:
3784:
in Berlin: Zwischen archäologischer Beobachtung und geometrischer Vermessung".
3781:
3167:
3155:
3150:)) algorithm for generating a Voronoi diagram from a set of points in a plane.
3139:
3090:
2979:
2936:
2903:
2794:
2750:
2706:
2007:
of points in two or three dimensions give rise to many familiar tessellations.
1964:
498:
490:
71:
5274:
5252:
5235:
4936:
4918:
4773:
4581:
4243:
3963:"Fundamental physical cellular constraints drive self-organization of tissues"
3885:
3802:
2410:
6420:
5789:
5753:
5553:
5541:
5399:
5199:
5022:
4988:
4946:
4914:
4675:
4667:
4628:
4456:
4394:
4343:
3789:
3681:
3643:
7.4 Farthest-Point Voronoi Diagrams. Includes a description of the algorithm.
3616:
3567:
3289:
3083:
2982:
data structure can be built on top of the Voronoi diagram in order to answer
2820:
2717:
2428:
2282:; then the farthest-point Voronoi diagram is a subdivision of the plane into
2141:
Higher-order Voronoi diagrams can be generated recursively. To generate the
2110:, we get rectangular tiles with the points not necessarily at their centers.
1996:
1957:
5309:
5115:
5090:
Proceedings of the twenty-seventh annual symposium on Computational geometry
4846:
4620:
3978:
3671:, contains a simple algorithm to compute the farthest-point Voronoi diagram.
2540:
Voronoi diagrams are also related to other geometric structures such as the
2079:
Certain body-centered tetragonal lattices give a tessellation of space with
2071:
Certain body-centered tetragonal lattices give a tessellation of space with
1991:
1862:
1848:
19:
5688:
5425:
5355:
4892:
4300:
4166:
4040:
3996:
3893:
3737:
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing
3688:; Verdonschot, Sander (2016). "Realizing farthest-point Voronoi diagrams".
3608:
3575:
3294:
3118:
2939:, Voronoi diagrams can be used to evaluate the Freight Loading Zone system.
2925:
2856:
2805:
2736:
2710:
2553:
1917:
534:
494:
48:
4251:
3744:
3417:
5674:
5257:-dimensional Delaunay tessellation with application to Voronoi polytopes"
5070:
3777:
3732:
3439:
Okabe, Atsuyuki; Boots, Barry; Sugihara, Kokichi; Chiu, Sung Nok (2000).
2831:
2698:
2541:
2244:
1976:
1921:
1910:
32:
4870:
4650:
Teruel, Enrique; Aragues, Rosario; López-Nicolás, Gonzalo (April 2021).
1824:{\displaystyle d\left=\left|a_{1}-b_{1}\right|+\left|a_{2}-b_{2}\right|}
5743:
4787:
2907:
2138:
nearest neighbors. Higher-order Voronoi diagrams also subdivide space.
1972:
1884:
111:
107:
4282:
3960:
3936:
5763:
5748:
5664:
5640:
5300:
5044:
Spatial Tessellations — Concepts and Applications of Voronoi Diagrams
4944:
3607:
3441:
Spatial Tessellations – Concepts and Applications of Voronoi Diagrams
3104:
2881:, Voronoi diagrams can be used to represent free volumes of polymers.
2761:
2431:
is a type of Voronoi diagram defined from a set of circles using the
2384:
1941:
1117:), but again, in many cases only finitely many sites are considered.
3868:
2830:, Voronoi diagrams are used to calculate profiles of an object with
5532:
4431:
4141:
3046:, Voronoi diagrams can be used in derivations of the capacity of a
3003:
2988:
2961:
2914:
2775:
2740:
A Voronoi tessellation emerges by radial growth from seeds outward.
2570:
results in the formation of polygons around the stations. The area
5098:
4652:"A Practical Method to Cover Evenly a Dynamic Region With a Swarm"
4086:
1920:
and the distance to each site is attained (e.g., when a site is a
493:. When two cells in the Voronoi diagram share a boundary, it is a
2964:, some of the control strategies and path planning algorithms of
2789:, ligand-binding sites are transformed into Voronoi diagrams for
2768:
2746:
2153: − 1)-order diagram and replace each cell generated by
1913:
if and only if their Voronoi cells share an infinitely long side.
628:
202:
is one of these given points, and its corresponding Voronoi cell
103:
4522:
Singh, K.; Sadeghi, F.; Correns, M.; Blass, T. (December 2019).
3495:
Transactions on Large-Scale Data- and Knowledge-Centered Systems
2672:{\displaystyle {\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}}
283:
is less than or equal to the minimum distance to any other site
5324:
4603:
Cortes, J.; Martinez, S.; Karatas, T.; Bullo, F. (April 2004).
3316:"8.11 Nearest neighbours: Thiessen (Dirichlet/Voroni) polygons"
3313:
3240:
3D Voronoi mesh of 25 random points with 0.3 opacity and points
2943:
2702:
4774:"Mark DiMarco: User Interface Algorithms [JSConf2014]"
4561:
Niu, Hanlin; Savvaris, Al; Tsourdos, Antonios; Ji, Ze (2019).
4009:
2778:, Voronoi diagrams are used to model domains of danger in the
4364:
4313:
3917:
Three-Dimensional Image Processing (3Dip) and Applications II
2918:
2910:) space of crystals which have the symmetry of a space group.
1971:-dimensional case in 1908. Voronoi diagrams that are used in
1060:
624:
5458:
4265:
Pimpinelli, Alberto; Tumbek, Levent; Winkler, Adolf (2014).
3342:
5313:
3252:
3D Voronoi mesh of 25 random points convex polyhedra pieces
5171:
10.1175/1520-0493(1911)39<1082b:pafla>2.0.co;2
4649:
4602:
4409:
3956:
3954:
2968:
are based on the Voronoi partitioning of the environment.
2823:
methods, e.g. as in the moving-mesh cosmology code AREPO.
2427:, in this case some of the Voronoi cells may be empty. A
1902:
corresponds to two adjacent cells in the Voronoi diagram.
1841:
Voronoi diagrams of 20 points under two different metrics
229:
consists of every point in the Euclidean plane for which
5290:
4521:
4502:
3735:(2002). "Space-efficient approximate Voronoi diagrams".
3730:
3680:
4358:
4264:
3951:
3804:
Voronoi Cells & Geodesic Distances - Sabouroff head
3468:. Exercise 2.9: Cambridge University Press. p. 60.
3134:
and then obtaining its dual. Direct algorithms include
1940:
Informal use of Voronoi diagrams can be traced back to
5037:
3438:
3216:
Random points in 3D for forming a 3D Voronoi partition
2488:
1350:
1323:
1296:
1269:
1242:
1215:
1195:
1168:
1141:
1069:
924:
904:
825:
805:
785:
758:
752:
is not greater than their distance to the other sites
731:
711:
684:
657:
637:
583:
563:
543:
519:
4560:
2921:), as an aircraft progresses through its flight plan.
2609:
2576:
2544:(which has found applications in image segmentation,
2468:
2448:
1666:
1454:
1417:
1390:
1209:
be the set of all points in the Euclidean space. Let
946:
469:
442:
405:
370:
343:
316:
289:
262:
235:
208:
181:
128:
4415:
4258:
4215:
4957:(2nd revised ed.). Springer. pp. 47–163.
4887:
3775:
2181:} with a Voronoi diagram generated on the set
4307:
2671:
2595:
2524:
2474:
2454:
1823:
1642:
1430:
1403:
1363:
1336:
1309:
1282:
1255:
1228:
1201:
1181:
1154:
1101:
1049:
930:
910:
890:
811:
791:
771:
744:
717:
697:
670:
643:
615:
569:
549:
525:
481:
455:
428:
383:
356:
329:
302:
275:
248:
221:
194:
163:
23:20 points and their Voronoi cells (larger version
5156:(7). American Meteorological Society: 1082–1089.
5005:
3853:
2687:
2394:
2192:
891:{\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}}
70:The Voronoi diagram is named after mathematician
6418:
4221:
3463:
2902:is the Voronoi tessellation of a solid, and the
2113:
848:
5316:, the Computational Geometry Algorithms Library
5224:Journal für die Reine und Angewandte Mathematik
5188:Journal für die Reine und Angewandte Mathematik
5011:Journal für die Reine und Angewandte Mathematik
4714:(International ed.). McGraw-Hill. p.
3492:
4970:Includes a description of Fortune's algorithm.
4605:"Coverage control for mobile sensing networks"
4187:
3523:
3374:"2.8.1 Delaney, Varoni, and Thiessen Polygons"
3320:Principles of Geographical Information Systems
1236:be a point that generates its Voronoi region
5340:
4983:. Vol. 333. Springer. pp. 148–157.
3831:Party competition : an agent-based model
3828:
3378:Spatial Modeling Principles in Earth Sciences
4897:Voronoi Diagrams and Delaunay Triangulations
4792:Victorian Government Department of Education
4609:IEEE Transactions on Robotics and Automation
3796:
3769:
3702:
3464:Boyd, Stephen; Vandenberghe, Lieven (2004).
3204:Voronoi meshes can also be generated in 3D.
2514:
2500:
1120:In the particular case where the space is a
1044:
960:
885:
851:
158:
129:
4977:Computational Geometry and its Applications
4837:. In Olano, Marc; Séquin, Carlo H. (eds.).
4776:. 11 June 2014 – via www.youtube.com.
4181:
4014:Protein-Ligand Interactions and Drug Design
3603:
3601:
3493:Tran, Q. T.; Tainar, D.; Safar, M. (2009).
3400:
3006:, Voronoi diagrams can be used to find the
2906:is the Voronoi tessellation of reciprocal (
2057:lattice gives a tessellation of space with
2046:lattice gives a tessellation of space with
2035:lattice gives a tessellation of space with
5347:
5333:
3731:Sunil Arya, Sunil; Malamatos, Theocharis;
3349:Geographic Information Systems and Science
3322:. Oxford University Press. pp. 160–.
2683:Delaunay triangulation § Applications
1034:
1028:
5658:Dividing a square into similar rectangles
5273:
5169:
5097:
4935:
4430:
4290:
4271:The Journal of Physical Chemistry Letters
4194:. Penguin Publishing Group. p. 187.
4140:
4103:
4085:
3986:
3867:
3833:. Princeton: Princeton University Press.
3829:Laver, Michael; Sergenti, Ernest (2012).
2548:, and other computational applications),
2294:lies in the cell corresponding to a site
1371:, and so on. Then, as expressed by Tran
866:
838:
5214:
5178:
5146:"Precipitation averages for large areas"
5140:
4705:
4067:
3598:
3592:
3588:
3541:
2735:
2564:
2409:
1990:
1887:for a Voronoi diagram (in the case of a
651:. The Voronoi cell, or Voronoi region,
18:
4829:
4738:
3815:as described by Hölscher et al. cf.
3511:
2953:, Voronoi tessellation can be used for
1935:
898:denotes the distance between the point
6419:
5250:
4913:
4830:Rong, Guodong; Tan, Tiow Seng (2006).
4810:
3914:
3097:
2709:, which made use of a high-resolution
1162:is associated with a generator point
5720:
5570:
5470:
5366:
5328:
5291:
4974:
4126:
3652:
3486:
2525:{\textstyle O(n^{\lceil d/2\rceil })}
2145:-order Voronoi diagram from set
1891:with point sites) corresponds to the
256:is the nearest site: the distance to
164:{\displaystyle \{p_{1},\dots p_{n}\}}
5087:
5060:
4656:IEEE Robotics and Automation Letters
3708:Algorithms in Combinatorial Geometry
3684:; Grimm, Carsten; Palios, Leonidas;
3529:
3517:
1967:who defined and studied the general
508:
463:is the intersection of all of these
117:
4919:"Computing Dirichlet tessellations"
3786:Gedenkschrift für Georgios Despinis
3776:Hölscher, Tonio; Krömker, Susanne;
3371:
3228:3D Voronoi mesh of 25 random points
3021:while assessing the dataset from a
2731:
94:). Voronoi cells are also known as
13:
5721:
4945:de Berg, Mark; van Kreveld, Marc;
4481:. ARM Architecture. Archived from
4188:Steven Johnson (19 October 2006).
3075:, Voronoi diagrams are used to do
2865:1854 Broad Street cholera outbreak
2239:is the farthest point. A point of
1059:The Voronoi diagram is simply the
14:
6468:
5284:
4981:Lecture Notes in Computer Science
4739:Shenwai, Tanushree (2021-11-18).
3542:Senechal, Marjorie (1993-05-21).
3061:organic or lava-looking textures.
2290:, with the property that a point
2003:Voronoi tessellations of regular
1963:Voronoi diagrams are named after
627:(indexed collection) of nonempty
24:
5457:
5450:
5354:
4528:International Journal of Fatigue
4105:10.1111/j.1365-2966.2009.15715.x
3856:Bulletin of Mathematical Biology
3706:(2012) . "13.6 Power Diagrams".
3245:
3233:
3221:
3209:
3199:
1861:
1847:
337:, the points that are closer to
5038:Okabe, Atsuyuki; Boots, Barry;
4949:; Schwarzkopf, Otfried (2000).
4863:
4823:
4804:
4780:
4757:
4732:
4699:
4690:
4643:
4596:
4554:
4540:10.1016/j.ijfatigue.2019.105229
4515:
4496:
4471:
4120:
4061:
4003:
3908:
3847:
3822:
3724:
3696:
3674:
3646:
3582:
3535:
3194:Centroidal Voronoi tessellation
3184:and its generalization via the
2559:
1378:
489:half-spaces, and hence it is a
6457:Geographic information systems
4479:"GOLD COAST CULTURAL PRECINCT"
3655:Information Processing Letters
3457:
3432:
3394:
3365:
3336:
3307:
3285:Nearest-neighbor interpolation
3280:Natural neighbor interpolation
3036:
2972:
2871:
2688:Humanities and social sciences
2616:
2590:
2577:
2519:
2492:
2395:Generalizations and variations
2193:Farthest-point Voronoi diagram
1960:than to any other water pump.
1946:Peter Gustav Lejeune Dirichlet
1084:
1070:
1025:
1006:
997:
978:
870:
857:
842:
829:
598:
584:
92:Peter Gustav Lejeune Dirichlet
1:
5683:Regular Division of the Plane
5471:
4880:
3788:(in German). Athens, Greece:
3560:10.1126/science.260.5111.1170
3125:
2546:optical character recognition
2286:cells, one for each point in
2114:Higher-order Voronoi diagrams
2066:hexagonal prismatic honeycomb
1956:lived closer to the infected
1954:Broad Street cholera outbreak
1877:
1102:{\textstyle (R_{k})_{k\in K}}
616:{\textstyle (P_{k})_{k\in K}}
391:, or equally distant, form a
5367:
4023:10.1007/978-1-0716-1209-5_17
3817:doi:10.11588/heidok.00027985
3667:10.1016/0020-0190(91)90030-L
3443:(2nd ed.). John Wiley.
3345:"14.4.4.1 Thiessen polygons"
3023:coordinate-measuring machine
2817:computational fluid dynamics
2535:approximate Voronoi diagrams
2482:-dimensional space can have
2081:rhombo-hexagonal dodecahedra
2073:rhombo-hexagonal dodecahedra
799:is any index different from
705:is the set of all points in
577:be a set of indices and let
7:
5591:Architectonic and catoptric
5489:Aperiodic set of prototiles
4811:Haridy, Rich (2017-09-06).
4449:10.1103/physrevb.100.155402
3813:GigaMesh Software Framework
3257:
2836:High energy density physics
2799:Voronoi deformation density
2037:trapezo-rhombic dodecahedra
1986:
1965:Georgy Feodosievych Voronoy
1895:for the same set of points.
678:, associated with the site
10:
6473:
6442:Eponymous geometric shapes
5215:Voronoï, Georges (1908b).
5179:Voronoï, Georges (1908a).
4387:10.1103/PhysRevB.79.165415
4336:10.1103/PhysRevB.75.245312
4159:10.1103/PhysRevE.95.023306
3380:. Springer. pp. 57–.
2930:The Arts Centre Gold Coast
2834:and proton radiography in
2680:
2439:from the circle's center.
2437:squared Euclidean distance
2208:For a given set of points
1905:Assume the setting is the
429:{\displaystyle p_{j}p_{k}}
5876:
5803:
5772:
5734:
5730:
5716:
5577:
5571:
5566:
5479:
5466:
5448:
5375:
5362:
5251:Watson, David F. (1981).
5236:10.1515/crll.1908.134.198
5042:; Chiu, Sung Nok (2000).
4841:. ACM. pp. 109–116.
4706:Mitchell, Tom M. (1997).
4582:10.1017/S0373463318001005
4570:The Journal of Navigation
4244:10.1103/PhysRevB.53.10261
4068:Springel, Volker (2010).
3886:10.1007/s11538-009-9498-3
3497:. Springer. p. 357.
3186:Linde–Buzo–Gray algorithm
3111:
2991:. A large application is
2842:
2797:. This is done using the
631:(the sites) in the space
175:. In this case each site
5200:10.1515/crll.1908.133.97
5023:10.1515/crll.1850.40.209
4989:10.1007/3-540-50335-8_31
4668:10.1109/LRA.2021.3057568
3811:. Analysis using the
3478:: CS1 maint: location (
3351:. Wiley. pp. 333–.
3301:
2420:weighted Voronoi diagram
2278:} be the convex hull of
395:, whose boundary is the
5275:10.1093/comjnl/24.2.167
5116:10.1145/1998196.1998234
5046:(2nd ed.). Wiley.
4937:10.1093/comjnl/24.2.162
4847:10.1145/1111411.1111431
4621:10.1109/TRA.2004.824698
3979:10.15252/embj.201592374
3176:Jump Flooding Algorithm
3152:Bowyer–Watson algorithm
2787:computational chemistry
2755:bone microarchitecture.
2596:{\displaystyle (A_{i})}
2442:The Voronoi diagram of
2086:For the set of points (
537:with distance function
74:, and is also called a
16:Type of plane partition
6432:Computational geometry
5150:Monthly Weather Review
4955:Computational Geometry
3625:Computational Geometry
3275:Natural element method
3265:Delaunay triangulation
3132:Delaunay triangulation
3117:Ukrainian pastry chef
3030:Pólya's shires theorem
2741:
2673:
2597:
2526:
2476:
2456:
2415:
2033:hexagonal close-packed
2000:
1929:uniformly convex space
1900:closest pair of points
1893:Delaunay triangulation
1825:
1644:
1432:
1405:
1365:
1338:
1311:
1284:
1257:
1230:
1203:
1183:
1156:
1103:
1051:
932:
912:
892:
813:
793:
773:
746:
719:
699:
672:
645:
617:
571:
551:
527:
483:
457:
430:
397:perpendicular bisector
385:
358:
331:
304:
277:
250:
223:
196:
165:
88:Dirichlet tessellation
65:Delaunay triangulation
28:
5007:Lejeune Dirichlet, G.
4951:"7. Voronoi Diagrams"
3745:10.1145/509907.510011
3704:Edelsbrunner, Herbert
3418:10.1145/116873.116880
3406:ACM Computing Surveys
3059:procedurally generate
2828:computational physics
2810:signal-to-noise ratio
2739:
2695:classical archaeology
2674:
2598:
2565:Meteorology/Hydrology
2527:
2477:
2457:
2413:
1994:
1826:
1645:
1433:
1431:{\displaystyle P_{k}}
1406:
1404:{\displaystyle R_{k}}
1366:
1339:
1312:
1285:
1258:
1231:
1204:
1184:
1157:
1104:
1052:
933:
913:
893:
819:. In other words, if
814:
794:
774:
747:
720:
700:
673:
646:
618:
572:
552:
528:
484:
458:
456:{\displaystyle R_{k}}
431:
386:
384:{\displaystyle p_{j}}
359:
357:{\displaystyle p_{k}}
332:
330:{\displaystyle p_{j}}
310:. For one other site
305:
303:{\displaystyle p_{j}}
278:
276:{\displaystyle p_{k}}
251:
249:{\displaystyle p_{k}}
224:
222:{\displaystyle R_{k}}
197:
195:{\displaystyle p_{k}}
166:
80:Voronoi decomposition
22:
6447:Ukrainian inventions
5092:. pp. 254–263.
5071:10.1109/ISVD.2009.23
5065:. pp. 144–152.
4899:. World Scientific.
3739:. pp. 721–730.
3621:Schwarzkopf, Otfried
3008:largest empty circle
2607:
2574:
2486:
2466:
2446:
2401:Mahalanobis distance
2022:simple cubic lattice
1936:History and research
1664:
1452:
1415:
1388:
1348:
1321:
1294:
1267:
1240:
1213:
1193:
1166:
1139:
1067:
944:
922:
902:
823:
803:
783:
756:
729:
709:
682:
655:
635:
581:
561:
541:
517:
467:
440:
403:
368:
341:
314:
287:
260:
233:
206:
179:
126:
76:Voronoi tessellation
5162:1911MWRv...39R1082T
5142:Thiessen, Alfred H.
5108:2011arXiv1103.4125R
4441:2019PhRvB.100o5402L
4379:2009PhRvB..79p5415M
4328:2007PhRvB..75x5312F
4236:1996PhRvB..5310261M
4151:2017PhRvE..95b3306K
4096:2010MNRAS.401..791S
3929:2012SPIE.8290E..0PL
3878:2009arXiv0901.4469B
3554:(5111): 1170–1173.
3466:Convex Optimization
3372:Sen, Zekai (2016).
3136:Fortune's algorithm
3098:Civics and planning
2995:, commonly used in
2993:vector quantization
2966:multi-robot systems
2896:solid-state physics
2780:selfish herd theory
2372:between two points
2059:truncated octahedra
2048:rhombic dodecahedra
1111:geometry of numbers
482:{\displaystyle n-1}
6452:Russian inventions
6437:Eponymous diagrams
5293:Weisstein, Eric W.
4889:Aurenhammer, Franz
4373:(165415): 165415.
3686:Shewchuk, Jonathan
3627:(Third ed.).
3402:Aurenhammer, Franz
3190:k-means clustering
2812:on all the images.
2742:
2701:, the symmetry of
2669:
2593:
2522:
2472:
2452:
2416:
2405:Manhattan distance
2370:Euclidean distance
2149:, start with the (
2106:in a discrete set
2098:in a discrete set
2055:body-centred cubic
2044:face-centred cubic
2001:
1981:Alfred H. Thiessen
1916:If the space is a
1869:Manhattan distance
1855:Euclidean distance
1821:
1655:Manhattan distance
1640:
1443:Euclidean distance
1428:
1401:
1364:{\textstyle R_{3}}
1361:
1337:{\textstyle P_{3}}
1334:
1310:{\textstyle R_{2}}
1307:
1283:{\textstyle P_{2}}
1280:
1256:{\textstyle R_{1}}
1253:
1229:{\textstyle P_{1}}
1226:
1199:
1182:{\textstyle P_{k}}
1179:
1155:{\textstyle R_{k}}
1152:
1122:finite-dimensional
1099:
1047:
928:
908:
888:
809:
789:
772:{\textstyle P_{j}}
769:
745:{\textstyle P_{k}}
742:
725:whose distance to
715:
698:{\textstyle P_{k}}
695:
671:{\textstyle R_{k}}
668:
641:
613:
567:
547:
523:
479:
453:
426:
381:
354:
327:
300:
273:
246:
219:
192:
161:
100:Alfred H. Thiessen
29:
6427:Discrete geometry
6414:
6413:
6410:
6409:
6406:
6405:
5712:
5711:
5603:Computer graphics
5562:
5561:
5446:
5445:
5296:"Voronoi diagram"
5080:978-1-4244-4769-5
5040:Sugihara, Kokichi
4998:978-3-540-52055-9
4964:978-3-540-65620-3
4725:978-0-07-042807-2
4419:Physical Review B
4367:Physical Review B
4316:Physical Review B
4283:10.1021/jz500282t
4224:Physical Review B
4201:978-1-101-15853-1
4129:Physical Review E
4032:978-1-0716-1209-5
3937:10.1117/12.907371
3840:978-0-691-13903-6
3638:978-3-540-77974-2
3613:van Kreveld, Marc
3450:978-0-471-98635-5
3387:978-3-319-41758-5
3358:978-0-470-87001-3
3329:978-0-19-874284-5
3182:Lloyd's algorithm
3055:computer graphics
2955:surface roughness
2951:surface metrology
2900:Wigner-Seitz cell
2886:materials science
2850:medical diagnosis
2725:political science
2667:
2619:
2550:straight skeleton
2475:{\displaystyle d}
2455:{\displaystyle n}
2303:if and only if d(
2269:, ...,
2226:, ...,
2171:, ...,
1958:Broad Street pump
1638:
1032:
509:Formal definition
393:closed half-space
118:The simplest case
96:Thiessen polygons
84:Voronoi partition
6464:
5732:
5731:
5718:
5717:
5670:Conway criterion
5597:Circle Limit III
5568:
5567:
5501:Einstein problem
5468:
5467:
5461:
5454:
5390:Schwarz triangle
5364:
5363:
5349:
5342:
5335:
5326:
5325:
5310:Voronoi Diagrams
5306:
5305:
5279:
5277:
5247:
5230:(134): 198–287.
5221:
5211:
5185:
5175:
5173:
5137:
5101:
5084:
5057:
5034:
5002:
4968:
4941:
4939:
4910:
4875:
4874:
4867:
4861:
4860:
4836:
4827:
4821:
4820:
4808:
4802:
4801:
4799:
4798:
4788:"Find my School"
4784:
4778:
4777:
4761:
4755:
4754:
4752:
4751:
4736:
4730:
4729:
4713:
4710:Machine Learning
4703:
4697:
4694:
4688:
4687:
4662:(2): 1359–1366.
4647:
4641:
4640:
4600:
4594:
4593:
4567:
4558:
4552:
4551:
4519:
4513:
4512:
4500:
4494:
4493:
4491:
4490:
4475:
4469:
4468:
4434:
4413:
4407:
4406:
4362:
4356:
4355:
4311:
4305:
4304:
4294:
4262:
4256:
4255:
4219:
4213:
4212:
4210:
4208:
4185:
4179:
4178:
4144:
4124:
4118:
4117:
4107:
4089:
4065:
4059:
4058:
4056:
4055:
4007:
4001:
4000:
3990:
3967:The EMBO Journal
3958:
3949:
3948:
3912:
3906:
3905:
3871:
3862:(7): 1696–1731.
3851:
3845:
3844:
3826:
3820:
3805:
3800:
3794:
3793:
3773:
3767:
3766:
3728:
3722:
3721:
3700:
3694:
3693:
3678:
3672:
3670:
3650:
3644:
3642:
3605:
3596:
3586:
3580:
3579:
3539:
3533:
3527:
3521:
3515:
3509:
3508:
3490:
3484:
3483:
3477:
3469:
3461:
3455:
3454:
3436:
3430:
3429:
3398:
3392:
3391:
3369:
3363:
3362:
3340:
3334:
3333:
3311:
3270:Map segmentation
3249:
3237:
3225:
3213:
3079:classifications.
3073:machine learning
3066:robot navigation
3048:wireless network
2997:data compression
2984:nearest neighbor
2791:machine learning
2732:Natural sciences
2678:
2676:
2675:
2670:
2668:
2666:
2665:
2664:
2651:
2650:
2649:
2640:
2639:
2626:
2621:
2620:
2612:
2602:
2600:
2599:
2594:
2589:
2588:
2531:
2529:
2528:
2523:
2518:
2517:
2510:
2481:
2479:
2478:
2473:
2461:
2459:
2458:
2453:
2387:, with infinite
2385:topological tree
1865:
1851:
1830:
1828:
1827:
1822:
1820:
1816:
1815:
1814:
1802:
1801:
1784:
1780:
1779:
1778:
1766:
1765:
1748:
1744:
1743:
1739:
1738:
1737:
1725:
1724:
1707:
1703:
1702:
1701:
1689:
1688:
1649:
1647:
1646:
1641:
1639:
1637:
1636:
1631:
1627:
1626:
1625:
1613:
1612:
1594:
1593:
1588:
1584:
1583:
1582:
1570:
1569:
1554:
1549:
1545:
1544:
1540:
1539:
1538:
1526:
1525:
1508:
1504:
1503:
1502:
1490:
1489:
1464:
1463:
1437:
1435:
1434:
1429:
1427:
1426:
1411:of a given shop
1410:
1408:
1407:
1402:
1400:
1399:
1370:
1368:
1367:
1362:
1360:
1359:
1344:that generates
1343:
1341:
1340:
1335:
1333:
1332:
1316:
1314:
1313:
1308:
1306:
1305:
1290:that generates
1289:
1287:
1286:
1281:
1279:
1278:
1262:
1260:
1259:
1254:
1252:
1251:
1235:
1233:
1232:
1227:
1225:
1224:
1208:
1206:
1205:
1200:
1188:
1186:
1185:
1180:
1178:
1177:
1161:
1159:
1158:
1153:
1151:
1150:
1129:convex polytopes
1108:
1106:
1105:
1100:
1098:
1097:
1082:
1081:
1056:
1054:
1053:
1048:
1033:
1030:
1024:
1023:
996:
995:
956:
955:
937:
935:
934:
929:
917:
915:
914:
909:
897:
895:
894:
889:
818:
816:
815:
810:
798:
796:
795:
790:
778:
776:
775:
770:
768:
767:
751:
749:
748:
743:
741:
740:
724:
722:
721:
716:
704:
702:
701:
696:
694:
693:
677:
675:
674:
669:
667:
666:
650:
648:
647:
642:
622:
620:
619:
614:
612:
611:
596:
595:
576:
574:
573:
568:
556:
554:
553:
548:
532:
530:
529:
524:
488:
486:
485:
480:
462:
460:
459:
454:
452:
451:
435:
433:
432:
427:
425:
424:
415:
414:
399:of line segment
390:
388:
387:
382:
380:
379:
363:
361:
360:
355:
353:
352:
336:
334:
333:
328:
326:
325:
309:
307:
306:
301:
299:
298:
282:
280:
279:
274:
272:
271:
255:
253:
252:
247:
245:
244:
228:
226:
225:
220:
218:
217:
201:
199:
198:
193:
191:
190:
170:
168:
167:
162:
157:
156:
141:
140:
6472:
6471:
6467:
6466:
6465:
6463:
6462:
6461:
6417:
6416:
6415:
6402:
5879:
5872:
5805:
5799:
5768:
5726:
5708:
5573:
5558:
5475:
5462:
5456:
5455:
5442:
5433:Wallpaper group
5371:
5358:
5353:
5287:
5282:
5253:"Computing the
5219:
5194:(133): 97–178.
5183:
5126:
5081:
5054:
5017:(40): 209–227.
4999:
4965:
4907:
4891:; Klein, Rolf;
4883:
4878:
4869:
4868:
4864:
4857:
4834:
4828:
4824:
4809:
4805:
4796:
4794:
4786:
4785:
4781:
4772:
4769:Wayback Machine
4762:
4758:
4749:
4747:
4737:
4733:
4726:
4704:
4700:
4695:
4691:
4648:
4644:
4601:
4597:
4565:
4559:
4555:
4520:
4516:
4511:. 11 (5), 1276.
4501:
4497:
4488:
4486:
4477:
4476:
4472:
4414:
4410:
4363:
4359:
4312:
4308:
4263:
4259:
4230:(15): 10261–7.
4220:
4216:
4206:
4204:
4202:
4186:
4182:
4125:
4121:
4066:
4062:
4053:
4051:
4033:
4008:
4004:
3959:
3952:
3913:
3909:
3852:
3848:
3841:
3827:
3823:
3803:
3801:
3797:
3774:
3770:
3755:
3733:Mount, David M.
3729:
3725:
3718:
3701:
3697:
3679:
3675:
3651:
3647:
3639:
3629:Springer-Verlag
3606:
3599:
3587:
3583:
3540:
3536:
3528:
3524:
3516:
3512:
3505:
3491:
3487:
3471:
3470:
3462:
3458:
3451:
3437:
3433:
3399:
3395:
3388:
3370:
3366:
3359:
3341:
3337:
3330:
3312:
3308:
3304:
3299:
3260:
3253:
3250:
3241:
3238:
3229:
3226:
3217:
3214:
3202:
3128:
3114:
3100:
3039:
2975:
2879:polymer physics
2874:
2845:
2734:
2697:, specifically
2690:
2685:
2660:
2656:
2652:
2645:
2641:
2635:
2631:
2627:
2625:
2611:
2610:
2608:
2605:
2604:
2584:
2580:
2575:
2572:
2571:
2567:
2562:
2506:
2499:
2495:
2487:
2484:
2483:
2467:
2464:
2463:
2447:
2444:
2443:
2397:
2359:
2350:
2337:
2328:
2315:
2302:
2277:
2268:
2261:
2234:
2225:
2218:
2195:
2180:
2170:
2163:
2116:
2026:cubic honeycomb
1989:
1938:
1907:Euclidean plane
1889:Euclidean space
1880:
1875:
1874:
1873:
1872:
1871:
1866:
1858:
1857:
1852:
1843:
1842:
1810:
1806:
1797:
1793:
1792:
1788:
1774:
1770:
1761:
1757:
1756:
1752:
1733:
1729:
1720:
1716:
1715:
1711:
1697:
1693:
1684:
1680:
1679:
1675:
1674:
1670:
1665:
1662:
1661:
1632:
1621:
1617:
1608:
1604:
1603:
1599:
1598:
1589:
1578:
1574:
1565:
1561:
1560:
1556:
1555:
1553:
1534:
1530:
1521:
1517:
1516:
1512:
1498:
1494:
1485:
1481:
1480:
1476:
1475:
1471:
1459:
1455:
1453:
1450:
1449:
1422:
1418:
1416:
1413:
1412:
1395:
1391:
1389:
1386:
1385:
1381:
1355:
1351:
1349:
1346:
1345:
1328:
1324:
1322:
1319:
1318:
1301:
1297:
1295:
1292:
1291:
1274:
1270:
1268:
1265:
1264:
1247:
1243:
1241:
1238:
1237:
1220:
1216:
1214:
1211:
1210:
1194:
1191:
1190:
1173:
1169:
1167:
1164:
1163:
1146:
1142:
1140:
1137:
1136:
1125:Euclidean space
1115:crystallography
1087:
1083:
1077:
1073:
1068:
1065:
1064:
1029:
1019:
1015:
991:
987:
951:
947:
945:
942:
941:
923:
920:
919:
918:and the subset
903:
900:
899:
824:
821:
820:
804:
801:
800:
784:
781:
780:
763:
759:
757:
754:
753:
736:
732:
730:
727:
726:
710:
707:
706:
689:
685:
683:
680:
679:
662:
658:
656:
653:
652:
636:
633:
632:
601:
597:
591:
587:
582:
579:
578:
562:
559:
558:
542:
539:
538:
518:
515:
514:
511:
468:
465:
464:
447:
443:
441:
438:
437:
420:
416:
410:
406:
404:
401:
400:
375:
371:
369:
366:
365:
348:
344:
342:
339:
338:
321:
317:
315:
312:
311:
294:
290:
288:
285:
284:
267:
263:
261:
258:
257:
240:
236:
234:
231:
230:
213:
209:
207:
204:
203:
186:
182:
180:
177:
176:
173:Euclidean plane
152:
148:
136:
132:
127:
124:
123:
120:
37:Voronoi diagram
17:
12:
11:
5:
6470:
6460:
6459:
6454:
6449:
6444:
6439:
6434:
6429:
6412:
6411:
6408:
6407:
6404:
6403:
6401:
6400:
6395:
6390:
6385:
6380:
6375:
6370:
6365:
6360:
6355:
6350:
6345:
6340:
6335:
6330:
6325:
6320:
6315:
6310:
6305:
6300:
6295:
6290:
6285:
6280:
6275:
6270:
6265:
6260:
6255:
6250:
6245:
6240:
6235:
6230:
6225:
6220:
6215:
6210:
6205:
6200:
6195:
6190:
6185:
6180:
6175:
6170:
6165:
6160:
6155:
6150:
6145:
6140:
6135:
6130:
6125:
6120:
6115:
6110:
6105:
6100:
6095:
6090:
6085:
6080:
6075:
6070:
6065:
6060:
6055:
6050:
6045:
6040:
6035:
6030:
6025:
6020:
6015:
6010:
6005:
6000:
5995:
5990:
5985:
5980:
5975:
5970:
5965:
5960:
5955:
5950:
5945:
5940:
5935:
5930:
5925:
5920:
5915:
5910:
5905:
5900:
5895:
5890:
5884:
5882:
5874:
5873:
5871:
5870:
5865:
5860:
5855:
5850:
5845:
5840:
5835:
5830:
5825:
5820:
5815:
5809:
5807:
5801:
5800:
5798:
5797:
5792:
5787:
5782:
5776:
5774:
5770:
5769:
5767:
5766:
5761:
5756:
5751:
5746:
5740:
5738:
5728:
5727:
5714:
5713:
5710:
5709:
5707:
5706:
5701:
5696:
5691:
5686:
5679:
5678:
5677:
5672:
5662:
5661:
5660:
5655:
5650:
5645:
5644:
5643:
5630:
5625:
5620:
5615:
5610:
5605:
5600:
5593:
5588:
5578:
5575:
5574:
5564:
5563:
5560:
5559:
5557:
5556:
5551:
5546:
5545:
5544:
5530:
5525:
5520:
5515:
5510:
5509:
5508:
5506:Socolar–Taylor
5498:
5497:
5496:
5486:
5484:Ammann–Beenker
5480:
5477:
5476:
5464:
5463:
5449:
5447:
5444:
5443:
5441:
5440:
5435:
5430:
5429:
5428:
5423:
5418:
5407:Uniform tiling
5404:
5403:
5402:
5392:
5387:
5382:
5376:
5373:
5372:
5360:
5359:
5352:
5351:
5344:
5337:
5329:
5323:
5322:
5317:
5307:
5286:
5285:External links
5283:
5281:
5280:
5268:(2): 167–172.
5248:
5212:
5176:
5138:
5124:
5085:
5079:
5058:
5052:
5035:
5003:
4997:
4972:
4963:
4947:Overmars, Mark
4942:
4930:(2): 162–166.
4915:Bowyer, Adrian
4911:
4906:978-9814447638
4905:
4884:
4882:
4879:
4877:
4876:
4862:
4855:
4822:
4803:
4779:
4756:
4731:
4724:
4698:
4689:
4642:
4615:(2): 243–255.
4595:
4576:(4): 850–874.
4553:
4514:
4509:Sustainability
4495:
4470:
4425:(15): 155402.
4408:
4357:
4322:(24): 245312.
4306:
4257:
4214:
4200:
4180:
4119:
4080:(2): 791–851.
4060:
4031:
4002:
3950:
3907:
3846:
3839:
3821:
3795:
3782:Kopf Sabouroff
3768:
3753:
3723:
3716:
3695:
3682:Biedl, Therese
3673:
3661:(3): 121–125.
3645:
3637:
3617:Overmars, Mark
3597:
3581:
3534:
3522:
3510:
3503:
3485:
3456:
3449:
3431:
3412:(3): 345–405.
3393:
3386:
3364:
3357:
3335:
3328:
3305:
3303:
3300:
3298:
3297:
3292:
3287:
3282:
3277:
3272:
3267:
3261:
3259:
3256:
3255:
3254:
3251:
3244:
3242:
3239:
3232:
3230:
3227:
3220:
3218:
3215:
3208:
3201:
3198:
3127:
3124:
3123:
3122:
3113:
3110:
3109:
3108:
3099:
3096:
3095:
3094:
3091:user interface
3087:
3080:
3069:
3064:In autonomous
3062:
3051:
3038:
3035:
3034:
3033:
3026:
3011:
3000:
2980:point location
2974:
2971:
2970:
2969:
2958:
2947:
2940:
2937:urban planning
2933:
2922:
2911:
2904:Brillouin zone
2892:
2889:
2882:
2873:
2870:
2869:
2868:
2853:
2844:
2841:
2840:
2839:
2824:
2813:
2802:
2795:atomic charges
2783:
2772:
2765:
2758:
2733:
2730:
2729:
2728:
2721:
2714:
2707:Sabouroff head
2689:
2686:
2663:
2659:
2655:
2648:
2644:
2638:
2634:
2630:
2624:
2618:
2615:
2592:
2587:
2583:
2579:
2566:
2563:
2561:
2558:
2521:
2516:
2513:
2509:
2505:
2502:
2498:
2494:
2491:
2471:
2451:
2433:power distance
2396:
2393:
2355:
2346:
2333:
2324:
2311:
2298:
2273:
2266:
2259:
2255: = {
2230:
2223:
2216:
2212: = {
2194:
2191:
2175:
2168:
2161:
2157: = {
2115:
2112:
2077:
2076:
2069:
2062:
2051:
2040:
2029:
2018:
1988:
1985:
1937:
1934:
1933:
1932:
1925:
1914:
1903:
1896:
1879:
1876:
1867:
1860:
1859:
1853:
1846:
1845:
1844:
1840:
1839:
1838:
1837:
1833:
1832:
1819:
1813:
1809:
1805:
1800:
1796:
1791:
1787:
1783:
1777:
1773:
1769:
1764:
1760:
1755:
1751:
1747:
1742:
1736:
1732:
1728:
1723:
1719:
1714:
1710:
1706:
1700:
1696:
1692:
1687:
1683:
1678:
1673:
1669:
1651:
1650:
1635:
1630:
1624:
1620:
1616:
1611:
1607:
1602:
1597:
1592:
1587:
1581:
1577:
1573:
1568:
1564:
1559:
1552:
1548:
1543:
1537:
1533:
1529:
1524:
1520:
1515:
1511:
1507:
1501:
1497:
1493:
1488:
1484:
1479:
1474:
1470:
1467:
1462:
1458:
1425:
1421:
1398:
1394:
1380:
1377:
1358:
1354:
1331:
1327:
1304:
1300:
1277:
1273:
1250:
1246:
1223:
1219:
1202:{\textstyle X}
1198:
1176:
1172:
1149:
1145:
1096:
1093:
1090:
1086:
1080:
1076:
1072:
1046:
1043:
1040:
1037:
1027:
1022:
1018:
1014:
1011:
1008:
1005:
1002:
999:
994:
990:
986:
983:
980:
977:
974:
971:
968:
965:
962:
959:
954:
950:
931:{\textstyle A}
927:
911:{\textstyle x}
907:
887:
884:
881:
878:
875:
872:
869:
865:
862:
859:
856:
853:
850:
847:
844:
841:
837:
834:
831:
828:
812:{\textstyle k}
808:
792:{\textstyle j}
788:
766:
762:
739:
735:
718:{\textstyle X}
714:
692:
688:
665:
661:
644:{\textstyle X}
640:
610:
607:
604:
600:
594:
590:
586:
570:{\textstyle K}
566:
550:{\textstyle d}
546:
526:{\textstyle X}
522:
510:
507:
491:convex polygon
478:
475:
472:
450:
446:
423:
419:
413:
409:
378:
374:
351:
347:
324:
320:
297:
293:
270:
266:
243:
239:
216:
212:
189:
185:
160:
155:
151:
147:
144:
139:
135:
131:
119:
116:
110:, but also in
72:Georgy Voronoy
63:to that set's
15:
9:
6:
4:
3:
2:
6469:
6458:
6455:
6453:
6450:
6448:
6445:
6443:
6440:
6438:
6435:
6433:
6430:
6428:
6425:
6424:
6422:
6399:
6396:
6394:
6391:
6389:
6386:
6384:
6381:
6379:
6376:
6374:
6371:
6369:
6366:
6364:
6361:
6359:
6356:
6354:
6351:
6349:
6346:
6344:
6341:
6339:
6336:
6334:
6331:
6329:
6326:
6324:
6321:
6319:
6316:
6314:
6311:
6309:
6306:
6304:
6301:
6299:
6296:
6294:
6291:
6289:
6286:
6284:
6281:
6279:
6276:
6274:
6271:
6269:
6266:
6264:
6261:
6259:
6256:
6254:
6251:
6249:
6246:
6244:
6241:
6239:
6236:
6234:
6231:
6229:
6226:
6224:
6221:
6219:
6216:
6214:
6211:
6209:
6206:
6204:
6201:
6199:
6196:
6194:
6191:
6189:
6186:
6184:
6181:
6179:
6176:
6174:
6171:
6169:
6166:
6164:
6161:
6159:
6156:
6154:
6151:
6149:
6146:
6144:
6141:
6139:
6136:
6134:
6131:
6129:
6126:
6124:
6121:
6119:
6116:
6114:
6111:
6109:
6106:
6104:
6101:
6099:
6096:
6094:
6091:
6089:
6086:
6084:
6081:
6079:
6076:
6074:
6071:
6069:
6066:
6064:
6061:
6059:
6056:
6054:
6051:
6049:
6046:
6044:
6041:
6039:
6036:
6034:
6031:
6029:
6026:
6024:
6021:
6019:
6016:
6014:
6011:
6009:
6006:
6004:
6001:
5999:
5996:
5994:
5991:
5989:
5986:
5984:
5981:
5979:
5976:
5974:
5971:
5969:
5966:
5964:
5961:
5959:
5956:
5954:
5951:
5949:
5946:
5944:
5941:
5939:
5936:
5934:
5931:
5929:
5926:
5924:
5921:
5919:
5916:
5914:
5911:
5909:
5906:
5904:
5901:
5899:
5896:
5894:
5891:
5889:
5886:
5885:
5883:
5881:
5875:
5869:
5866:
5864:
5861:
5859:
5856:
5854:
5851:
5849:
5846:
5844:
5841:
5839:
5836:
5834:
5831:
5829:
5826:
5824:
5821:
5819:
5816:
5814:
5811:
5810:
5808:
5802:
5796:
5793:
5791:
5788:
5786:
5783:
5781:
5778:
5777:
5775:
5771:
5765:
5762:
5760:
5757:
5755:
5752:
5750:
5747:
5745:
5742:
5741:
5739:
5737:
5733:
5729:
5725:
5719:
5715:
5705:
5702:
5700:
5697:
5695:
5692:
5690:
5687:
5685:
5684:
5680:
5676:
5673:
5671:
5668:
5667:
5666:
5663:
5659:
5656:
5654:
5651:
5649:
5646:
5642:
5639:
5638:
5637:
5634:
5633:
5631:
5629:
5626:
5624:
5621:
5619:
5616:
5614:
5611:
5609:
5606:
5604:
5601:
5599:
5598:
5594:
5592:
5589:
5587:
5583:
5580:
5579:
5576:
5569:
5565:
5555:
5552:
5550:
5547:
5543:
5540:
5539:
5538:
5534:
5531:
5529:
5526:
5524:
5521:
5519:
5516:
5514:
5511:
5507:
5504:
5503:
5502:
5499:
5495:
5492:
5491:
5490:
5487:
5485:
5482:
5481:
5478:
5474:
5469:
5465:
5460:
5453:
5439:
5436:
5434:
5431:
5427:
5424:
5422:
5419:
5417:
5414:
5413:
5412:
5408:
5405:
5401:
5398:
5397:
5396:
5393:
5391:
5388:
5386:
5383:
5381:
5378:
5377:
5374:
5370:
5365:
5361:
5357:
5350:
5345:
5343:
5338:
5336:
5331:
5330:
5327:
5321:
5318:
5315:
5311:
5308:
5303:
5302:
5297:
5294:
5289:
5288:
5276:
5271:
5267:
5264:
5263:
5258:
5256:
5249:
5245:
5241:
5237:
5233:
5229:
5225:
5218:
5213:
5209:
5205:
5201:
5197:
5193:
5189:
5182:
5177:
5172:
5167:
5163:
5159:
5155:
5151:
5147:
5144:(July 1911).
5143:
5139:
5135:
5131:
5127:
5125:9781450306829
5121:
5117:
5113:
5109:
5105:
5100:
5095:
5091:
5086:
5082:
5076:
5072:
5068:
5064:
5059:
5055:
5053:0-471-98635-6
5049:
5045:
5041:
5036:
5032:
5028:
5024:
5020:
5016:
5012:
5008:
5004:
5000:
4994:
4990:
4986:
4982:
4978:
4973:
4971:
4966:
4960:
4956:
4952:
4948:
4943:
4938:
4933:
4929:
4926:
4925:
4920:
4916:
4912:
4908:
4902:
4898:
4894:
4893:Lee, Der-Tsai
4890:
4886:
4885:
4872:
4866:
4858:
4856:1-59593-295-X
4852:
4848:
4844:
4840:
4833:
4826:
4818:
4814:
4807:
4793:
4789:
4783:
4775:
4770:
4766:
4760:
4746:
4742:
4735:
4727:
4721:
4717:
4712:
4711:
4702:
4693:
4685:
4681:
4677:
4673:
4669:
4665:
4661:
4657:
4653:
4646:
4638:
4634:
4630:
4626:
4622:
4618:
4614:
4610:
4606:
4599:
4591:
4587:
4583:
4579:
4575:
4571:
4564:
4557:
4549:
4545:
4541:
4537:
4533:
4529:
4525:
4518:
4510:
4506:
4499:
4485:on 2016-07-07
4484:
4480:
4474:
4466:
4462:
4458:
4454:
4450:
4446:
4442:
4438:
4433:
4428:
4424:
4420:
4412:
4404:
4400:
4396:
4392:
4388:
4384:
4380:
4376:
4372:
4368:
4361:
4353:
4349:
4345:
4341:
4337:
4333:
4329:
4325:
4321:
4317:
4310:
4302:
4298:
4293:
4288:
4284:
4280:
4276:
4272:
4268:
4261:
4253:
4249:
4245:
4241:
4237:
4233:
4229:
4225:
4218:
4203:
4197:
4193:
4192:
4184:
4176:
4172:
4168:
4164:
4160:
4156:
4152:
4148:
4143:
4138:
4135:(2): 023306.
4134:
4130:
4123:
4115:
4111:
4106:
4101:
4097:
4093:
4088:
4083:
4079:
4075:
4071:
4064:
4050:
4046:
4042:
4038:
4034:
4028:
4024:
4020:
4016:
4015:
4006:
3998:
3994:
3989:
3984:
3980:
3976:
3972:
3968:
3964:
3957:
3955:
3946:
3942:
3938:
3934:
3930:
3926:
3922:
3918:
3911:
3903:
3899:
3895:
3891:
3887:
3883:
3879:
3875:
3870:
3865:
3861:
3857:
3850:
3842:
3836:
3832:
3825:
3818:
3814:
3810:
3806:
3799:
3791:
3790:Benaki Museum
3787:
3783:
3780:(2020). "Der
3779:
3772:
3764:
3760:
3756:
3750:
3746:
3742:
3738:
3734:
3727:
3719:
3717:9783642615689
3713:
3709:
3705:
3699:
3691:
3687:
3683:
3677:
3668:
3664:
3660:
3656:
3649:
3640:
3634:
3630:
3626:
3622:
3618:
3614:
3610:
3609:de Berg, Mark
3604:
3602:
3594:
3593:Voronoï 1908b
3590:
3589:Voronoï 1908a
3585:
3577:
3573:
3569:
3565:
3561:
3557:
3553:
3549:
3545:
3538:
3531:
3526:
3519:
3514:
3506:
3504:9783642037214
3500:
3496:
3489:
3481:
3475:
3467:
3460:
3452:
3446:
3442:
3435:
3427:
3423:
3419:
3415:
3411:
3407:
3403:
3397:
3389:
3383:
3379:
3375:
3368:
3360:
3354:
3350:
3346:
3339:
3331:
3325:
3321:
3317:
3310:
3306:
3296:
3293:
3291:
3290:Power diagram
3288:
3286:
3283:
3281:
3278:
3276:
3273:
3271:
3268:
3266:
3263:
3262:
3248:
3243:
3236:
3231:
3224:
3219:
3212:
3207:
3206:
3205:
3200:Voronoi in 3D
3197:
3195:
3191:
3187:
3183:
3179:
3177:
3173:
3169:
3165:
3161:
3157:
3153:
3149:
3145:
3141:
3137:
3133:
3120:
3116:
3115:
3106:
3102:
3101:
3092:
3088:
3085:
3084:deep learning
3081:
3078:
3074:
3070:
3067:
3063:
3060:
3056:
3052:
3049:
3045:
3041:
3040:
3031:
3027:
3024:
3020:
3016:
3012:
3009:
3005:
3001:
2998:
2994:
2990:
2985:
2981:
2977:
2976:
2967:
2963:
2959:
2956:
2952:
2948:
2945:
2941:
2938:
2934:
2931:
2927:
2923:
2920:
2916:
2912:
2909:
2905:
2901:
2897:
2893:
2890:
2887:
2883:
2880:
2876:
2875:
2866:
2863:to study the
2862:
2858:
2854:
2851:
2847:
2846:
2837:
2833:
2829:
2825:
2822:
2821:finite volume
2818:
2814:
2811:
2807:
2803:
2800:
2796:
2792:
2788:
2784:
2781:
2777:
2773:
2770:
2766:
2763:
2759:
2756:
2752:
2748:
2744:
2743:
2738:
2726:
2722:
2719:
2718:dialectometry
2715:
2712:
2708:
2704:
2700:
2696:
2692:
2691:
2684:
2679:
2661:
2657:
2653:
2646:
2642:
2636:
2632:
2628:
2622:
2613:
2585:
2581:
2557:
2555:
2554:zone diagrams
2551:
2547:
2543:
2538:
2536:
2511:
2507:
2503:
2496:
2489:
2469:
2449:
2440:
2438:
2434:
2430:
2429:power diagram
2426:
2421:
2412:
2408:
2406:
2402:
2392:
2390:
2386:
2381:
2379:
2375:
2371:
2367:
2363:
2358:
2354:
2349:
2345:
2341:
2338: ∈
2336:
2332:
2327:
2323:
2319:
2314:
2310:
2306:
2301:
2297:
2293:
2289:
2285:
2281:
2276:
2272:
2265:
2258:
2254:
2250:
2246:
2242:
2238:
2233:
2229:
2222:
2215:
2211:
2206:
2204:
2200:
2197:For a set of
2190:
2188:
2185: −
2184:
2178:
2174:
2167:
2160:
2156:
2152:
2148:
2144:
2139:
2137:
2133:
2129:
2125:
2121:
2111:
2109:
2105:
2101:
2097:
2093:
2089:
2084:
2082:
2074:
2070:
2067:
2063:
2060:
2056:
2052:
2049:
2045:
2041:
2038:
2034:
2030:
2027:
2023:
2019:
2015:
2010:
2009:
2008:
2006:
1998:
1997:power diagram
1993:
1984:
1982:
1978:
1974:
1970:
1966:
1961:
1959:
1955:
1951:
1947:
1943:
1930:
1926:
1923:
1919:
1915:
1912:
1908:
1904:
1901:
1897:
1894:
1890:
1886:
1882:
1881:
1870:
1864:
1856:
1850:
1836:
1817:
1811:
1807:
1803:
1798:
1794:
1789:
1785:
1781:
1775:
1771:
1767:
1762:
1758:
1753:
1749:
1745:
1740:
1734:
1730:
1726:
1721:
1717:
1712:
1708:
1704:
1698:
1694:
1690:
1685:
1681:
1676:
1671:
1667:
1660:
1659:
1658:
1656:
1633:
1628:
1622:
1618:
1614:
1609:
1605:
1600:
1595:
1590:
1585:
1579:
1575:
1571:
1566:
1562:
1557:
1550:
1546:
1541:
1535:
1531:
1527:
1522:
1518:
1513:
1509:
1505:
1499:
1495:
1491:
1486:
1482:
1477:
1472:
1468:
1465:
1460:
1456:
1448:
1447:
1446:
1444:
1439:
1423:
1419:
1396:
1392:
1376:
1374:
1356:
1352:
1329:
1325:
1302:
1298:
1275:
1271:
1248:
1244:
1221:
1217:
1196:
1174:
1170:
1147:
1143:
1133:
1130:
1126:
1123:
1118:
1116:
1112:
1094:
1091:
1088:
1078:
1074:
1062:
1057:
1041:
1038:
1035:
1020:
1016:
1012:
1009:
1003:
1000:
992:
988:
984:
981:
975:
972:
969:
966:
963:
957:
952:
948:
939:
925:
905:
882:
879:
876:
873:
867:
863:
860:
854:
845:
839:
835:
832:
826:
806:
786:
764:
760:
737:
733:
712:
690:
686:
663:
659:
638:
630:
626:
608:
605:
602:
592:
588:
564:
544:
536:
520:
506:
504:
500:
496:
492:
476:
473:
470:
448:
444:
421:
417:
411:
407:
398:
394:
376:
372:
349:
345:
322:
318:
295:
291:
268:
264:
241:
237:
214:
210:
187:
183:
174:
153:
149:
145:
142:
137:
133:
115:
113:
109:
105:
101:
97:
93:
89:
85:
81:
77:
73:
68:
66:
62:
58:
54:
50:
46:
42:
38:
34:
26:
21:
5698:
5694:Substitution
5689:Regular grid
5681:
5595:
5528:Quaquaversal
5426:Kisrhombille
5356:Tessellation
5299:
5265:
5260:
5254:
5227:
5223:
5191:
5187:
5153:
5149:
5089:
5062:
5043:
5014:
5010:
4976:
4969:
4954:
4927:
4922:
4896:
4865:
4838:
4825:
4816:
4806:
4795:. Retrieved
4791:
4782:
4765:Ghostarchive
4763:Archived at
4759:
4748:. Retrieved
4745:MarkTechPost
4744:
4734:
4709:
4701:
4692:
4659:
4655:
4645:
4612:
4608:
4598:
4573:
4569:
4556:
4531:
4527:
4517:
4508:
4498:
4487:. Retrieved
4483:the original
4473:
4422:
4418:
4411:
4370:
4366:
4360:
4319:
4315:
4309:
4277:(6): 995–8.
4274:
4270:
4260:
4227:
4223:
4217:
4205:. Retrieved
4190:
4183:
4132:
4128:
4122:
4077:
4073:
4063:
4052:. Retrieved
4013:
4005:
3973:(1): 77–88.
3970:
3966:
3920:
3916:
3910:
3859:
3855:
3849:
3830:
3824:
3798:
3785:
3778:Mara, Hubert
3771:
3736:
3726:
3707:
3698:
3689:
3676:
3658:
3654:
3648:
3624:
3584:
3551:
3547:
3537:
3525:
3513:
3494:
3488:
3465:
3459:
3440:
3434:
3409:
3405:
3396:
3377:
3367:
3348:
3338:
3319:
3309:
3295:Voronoi pole
3203:
3180:
3171:
3163:
3159:
3147:
3143:
3129:
3119:Dinara Kasko
2926:architecture
2857:epidemiology
2806:astrophysics
2711:polygon mesh
2568:
2560:Applications
2539:
2441:
2417:
2398:
2382:
2377:
2373:
2365:
2361:
2356:
2352:
2347:
2343:
2339:
2334:
2330:
2325:
2321:
2317:
2312:
2308:
2304:
2299:
2295:
2291:
2287:
2283:
2279:
2274:
2270:
2263:
2256:
2252:
2248:
2240:
2236:
2231:
2227:
2220:
2213:
2209:
2207:
2202:
2201:points the (
2198:
2196:
2186:
2182:
2176:
2172:
2165:
2158:
2154:
2150:
2146:
2142:
2140:
2135:
2131:
2127:
2123:
2119:
2117:
2107:
2103:
2099:
2095:
2091:
2087:
2085:
2078:
2002:
1968:
1962:
1939:
1918:normed space
1834:
1652:
1440:
1382:
1379:Illustration
1372:
1134:
1119:
1058:
940:
535:metric space
512:
495:line segment
121:
95:
87:
83:
79:
75:
69:
57:Voronoi cell
56:
49:tessellation
36:
30:
5724:vertex type
5582:Anisohedral
5537:Self-tiling
5380:Pythagorean
4871:"Shadertoy"
3869:0901.4469v1
3037:Informatics
2973:Mathematics
2872:Engineering
2832:Shadowgraph
2699:art history
2542:medial axis
2329:) for each
2245:convex hull
1977:meteorology
1922:compact set
1911:convex hull
55:, called a
33:mathematics
6421:Categories
5628:Pentagonal
5262:Comput. J.
4924:Comput. J.
4881:References
4797:2023-07-25
4750:2021-12-05
4534:: 105229.
4489:2014-04-28
4432:1902.10145
4207:16 October
4142:1607.04179
4054:2021-04-23
3923:: 82900P.
3754:1581134959
3126:Algorithms
3044:networking
2908:wavenumber
2681:See also:
2462:points in
2360:, where d(
2130:points in
2024:gives the
1973:geophysics
1885:dual graph
1878:Properties
112:visual art
108:technology
5736:Spherical
5704:Voderberg
5665:Prototile
5632:Problems
5608:Honeycomb
5586:Isohedral
5473:Aperiodic
5411:honeycomb
5395:Rectangle
5385:Rhombille
5301:MathWorld
5244:118441072
5208:116775758
5099:1103.4125
5031:199546675
4817:New Atlas
4684:232071627
4676:2377-3766
4629:2374-958X
4548:202213370
4465:119443529
4457:2469-9950
4395:1098-0121
4352:120017577
4344:1098-0121
4114:119241866
4087:0901.4107
4049:232338911
3568:0036-8075
3530:Reem 2011
3518:Reem 2009
3474:cite book
3105:Melbourne
3019:roundness
3015:roundness
2957:modeling.
2861:John Snow
2762:hydrology
2654:∑
2629:∑
2617:¯
2515:⌉
2501:⌈
2376:and
2368:) is the
2316:) > d(
2017:squares).
1950:John Snow
1944:in 1644.
1942:Descartes
1804:−
1768:−
1615:−
1572:−
1457:ℓ
1092:∈
1063:of cells
1039:≠
1001:≤
973:∣
967:∈
880:∈
874:∣
606:∈
474:−
146:…
41:partition
5818:V3.4.3.4
5653:Squaring
5648:Heesch's
5613:Isotoxal
5533:Rep-tile
5523:Pinwheel
5416:Coloring
5369:Periodic
5134:14639512
4917:(1981).
4895:(2013).
4767:and the
4590:67908628
4403:13719907
4301:24660052
4175:13326345
4167:28297858
4041:33759134
3997:26598531
3902:16074264
3894:20082148
3623:(2008).
3576:17806355
3258:See also
3004:geometry
2989:database
2962:robotics
2915:aviation
2776:ethology
2005:lattices
1987:Examples
779:, where
503:vertices
364:than to
98:, after
6278:6.4.8.4
6233:5.4.6.4
6193:4.12.16
6183:4.10.12
6153:V4.8.10
6128:V4.6.16
6118:V4.6.14
6018:3.6.4.6
6013:3.4.∞.4
6008:3.4.8.4
6003:3.4.7.4
5998:3.4.6.4
5948:3.∞.3.∞
5943:3.4.3.4
5938:3.8.3.8
5933:3.7.3.7
5928:3.6.3.8
5923:3.6.3.6
5918:3.5.3.6
5913:3.5.3.5
5908:3.4.3.∞
5903:3.4.3.8
5898:3.4.3.7
5893:3.4.3.6
5888:3.4.3.5
5843:3.4.6.4
5813:3.4.3.4
5806:regular
5773:Regular
5699:Voronoi
5623:Packing
5554:Truchet
5549:Socolar
5518:Penrose
5513:Gilbert
5438:Wythoff
5158:Bibcode
5104:Bibcode
4637:2022860
4437:Bibcode
4375:Bibcode
4324:Bibcode
4292:3962253
4252:9982595
4232:Bibcode
4147:Bibcode
4092:Bibcode
3988:4718000
3945:1505014
3925:Bibcode
3874:Bibcode
3809:YouTube
3763:1727373
3548:Science
3426:4613674
2801:method.
2769:ecology
2747:biology
2262:,
2219:,
2164:,
2134:as its
2094:) with
2090:,
1653:or the
1031:for all
938:, then
629:subsets
436:. Cell
171:in the
104:science
90:(after
86:, or a
6168:4.8.16
6163:4.8.14
6158:4.8.12
6148:4.8.10
6123:4.6.16
6113:4.6.14
6108:4.6.12
5878:Hyper-
5863:4.6.12
5636:Domino
5542:Sphinx
5421:Convex
5400:Domino
5242:
5206:
5132:
5122:
5077:
5050:
5029:
4995:
4961:
4903:
4853:
4722:
4682:
4674:
4635:
4627:
4588:
4546:
4463:
4455:
4401:
4393:
4350:
4342:
4299:
4289:
4250:
4198:
4173:
4165:
4112:
4047:
4039:
4029:
3995:
3985:
3943:
3900:
3892:
3837:
3761:
3751:
3714:
3635:
3574:
3566:
3501:
3447:
3424:
3384:
3355:
3326:
3166:)) to
3112:Bakery
2944:mining
2898:, the
2843:Health
2703:statue
2552:, and
2425:metric
2251:. Let
2014:square
1317:, and
1189:. Let
557:. Let
53:region
6283:(6.8)
6238:(5.6)
6173:4.8.∞
6143:(4.8)
6138:(4.7)
6133:4.6.∞
6103:(4.6)
6098:(4.5)
6068:4.∞.4
6063:4.8.4
6058:4.7.4
6053:4.6.4
6048:4.5.4
6028:(3.8)
6023:(3.7)
5993:(3.4)
5988:(3.4)
5880:bolic
5848:(3.6)
5804:Semi-
5675:Girih
5572:Other
5240:S2CID
5220:(PDF)
5204:S2CID
5184:(PDF)
5130:S2CID
5094:arXiv
5027:S2CID
4835:(PDF)
4680:S2CID
4633:S2CID
4586:S2CID
4566:(PDF)
4544:S2CID
4461:S2CID
4427:arXiv
4399:S2CID
4348:S2CID
4171:S2CID
4137:arXiv
4110:S2CID
4082:arXiv
4074:MNRAS
4045:S2CID
3941:S2CID
3898:S2CID
3864:arXiv
3759:S2CID
3422:S2CID
3302:Notes
3188:(aka
3154:, an
3138:, an
2919:ETOPS
2751:cells
2342:with
2122:, an
1373:et al
1061:tuple
625:tuple
623:be a
533:be a
45:plane
43:of a
39:is a
25:below
6368:8.16
6363:8.12
6333:7.14
6303:6.16
6298:6.12
6293:6.10
6253:5.12
6248:5.10
6203:4.16
6198:4.14
6188:4.12
6178:4.10
6038:3.16
6033:3.14
5853:3.12
5838:V3.6
5764:V4.n
5754:V3.n
5641:Wang
5618:List
5584:and
5535:and
5494:List
5409:and
5314:CGAL
5228:1908
5192:1908
5120:ISBN
5075:ISBN
5048:ISBN
5015:1850
4993:ISBN
4959:ISBN
4901:ISBN
4851:ISBN
4720:ISBN
4672:ISSN
4625:ISSN
4453:ISSN
4391:ISSN
4340:ISSN
4297:PMID
4248:PMID
4209:2017
4196:ISBN
4163:PMID
4037:PMID
4027:ISBN
3993:PMID
3921:8290
3890:PMID
3835:ISBN
3749:ISBN
3712:ISBN
3633:ISBN
3591:and
3572:PMID
3564:ISSN
3499:ISBN
3480:link
3445:ISBN
3382:ISBN
3353:ISBN
3324:ISBN
3162:log(
3146:log(
3077:1-NN
2753:and
2389:rays
2102:and
1975:and
1898:The
1883:The
1113:and
513:Let
106:and
82:, a
78:, a
61:dual
35:, a
6398:∞.8
6393:∞.6
6358:8.6
6328:7.8
6323:7.6
6288:6.8
6243:5.8
6208:4.∞
6043:3.∞
5968:3.4
5963:3.∞
5958:3.8
5953:3.7
5868:4.8
5858:4.∞
5833:3.6
5828:3.∞
5823:3.4
5759:4.n
5749:3.n
5722:By
5312:in
5270:doi
5232:doi
5196:doi
5166:doi
5112:doi
5067:doi
5019:doi
4985:doi
4932:doi
4843:doi
4716:233
4664:doi
4617:doi
4578:doi
4536:doi
4532:129
4445:doi
4423:100
4383:doi
4332:doi
4287:PMC
4279:doi
4240:doi
4155:doi
4100:doi
4078:401
4019:doi
3983:PMC
3975:doi
3933:doi
3882:doi
3807:on
3741:doi
3663:doi
3556:doi
3552:260
3414:doi
3103:In
3089:In
3071:In
3053:In
3042:In
3002:In
2960:In
2949:In
2942:In
2935:In
2924:In
2913:In
2894:In
2884:In
2877:In
2855:In
2848:In
2826:In
2815:In
2804:In
2785:In
2774:In
2767:In
2760:In
2745:In
2723:In
2716:In
2693:In
2403:or
2247:of
849:inf
499:ray
31:In
6423::
5298:.
5266:24
5259:.
5238:.
5226:.
5222:.
5202:.
5190:.
5186:.
5164:.
5154:39
5152:.
5148:.
5128:.
5118:.
5110:.
5102:.
5073:.
5025:.
5013:.
4991:.
4979:.
4953:.
4928:24
4921:.
4849:.
4815:.
4790:.
4771::
4743:.
4718:.
4678:.
4670:.
4658:.
4654:.
4631:.
4623:.
4613:20
4611:.
4607:.
4584:.
4574:72
4572:.
4568:.
4542:.
4530:.
4526:.
4507:.
4459:.
4451:.
4443:.
4435:.
4421:.
4397:.
4389:.
4381:.
4371:79
4369:.
4346:.
4338:.
4330:.
4320:75
4318:.
4295:.
4285:.
4273:.
4269:.
4246:.
4238:.
4228:53
4226:.
4169:.
4161:.
4153:.
4145:.
4133:95
4131:.
4108:.
4098:.
4090:.
4076:.
4072:.
4043:.
4035:.
4025:.
3991:.
3981:.
3971:35
3969:.
3965:.
3953:^
3939:.
3931:.
3919:.
3896:.
3888:.
3880:.
3872:.
3860:72
3858:.
3757:.
3747:.
3659:37
3657:.
3631:.
3619:;
3615:;
3611:;
3600:^
3570:.
3562:.
3550:.
3546:.
3476:}}
3472:{{
3420:.
3410:23
3408:.
3376:.
3347:.
3318:.
3032:).
2978:A
2556:.
2537:.
2418:A
2380:.
2364:,
2351:≠
2320:,
2307:,
2189:.
2179:−1
2083:.
2053:A
2042:A
2031:A
2020:A
1657::
1445::
1263:,
497:,
114:.
67:.
6388:∞
6383:∞
6378:∞
6373:∞
6353:8
6348:8
6343:8
6338:8
6318:7
6313:7
6308:7
6273:6
6268:6
6263:6
6258:6
6228:5
6223:5
6218:5
6213:5
6093:4
6088:4
6083:4
6078:4
6073:4
5983:3
5978:3
5973:3
5795:6
5790:4
5785:3
5780:2
5744:2
5348:e
5341:t
5334:v
5304:.
5278:.
5272::
5255:n
5246:.
5234::
5210:.
5198::
5174:.
5168::
5160::
5136:.
5114::
5106::
5096::
5083:.
5069::
5056:.
5033:.
5021::
5001:.
4987::
4967:.
4940:.
4934::
4909:.
4873:.
4859:.
4845::
4819:.
4800:.
4753:.
4728:.
4686:.
4666::
4660:6
4639:.
4619::
4592:.
4580::
4550:.
4538::
4492:.
4467:.
4447::
4439::
4429::
4405:.
4385::
4377::
4354:.
4334::
4326::
4303:.
4281::
4275:5
4254:.
4242::
4234::
4211:.
4177:.
4157::
4149::
4139::
4116:.
4102::
4094::
4084::
4057:.
4021::
3999:.
3977::
3947:.
3935::
3927::
3904:.
3884::
3876::
3866::
3843:.
3819:.
3792:.
3765:.
3743::
3720:.
3692:.
3669:.
3665::
3641:.
3595:.
3578:.
3558::
3532:.
3520:.
3507:.
3482:)
3453:.
3428:.
3416::
3390:.
3361:.
3332:.
3172:n
3170:(
3168:O
3164:n
3160:n
3158:(
3156:O
3148:n
3144:n
3142:(
3140:O
3086:.
3050:.
3025:.
2999:.
2932:.
2838:.
2782:.
2713:.
2662:i
2658:A
2647:i
2643:P
2637:i
2633:A
2623:=
2614:P
2591:)
2586:i
2582:A
2578:(
2520:)
2512:2
2508:/
2504:d
2497:n
2493:(
2490:O
2470:d
2450:n
2378:q
2374:p
2366:q
2362:p
2357:j
2353:p
2348:i
2344:h
2340:S
2335:j
2331:p
2326:j
2322:p
2318:q
2313:i
2309:h
2305:q
2300:i
2296:h
2292:q
2288:H
2284:k
2280:P
2275:k
2271:h
2267:2
2264:h
2260:1
2257:h
2253:H
2249:P
2241:P
2237:P
2232:n
2228:p
2224:2
2221:p
2217:1
2214:p
2210:S
2203:n
2199:n
2187:X
2183:S
2177:n
2173:x
2169:2
2166:x
2162:1
2159:x
2155:X
2151:n
2147:S
2143:n
2136:n
2132:S
2128:n
2124:n
2120:S
2108:Y
2104:y
2100:X
2096:x
2092:y
2088:x
2075:.
2068:.
2061:.
2050:.
2039:.
2028:.
1969:n
1831:.
1818:|
1812:2
1808:b
1799:2
1795:a
1790:|
1786:+
1782:|
1776:1
1772:b
1763:1
1759:a
1754:|
1750:=
1746:]
1741:)
1735:2
1731:b
1727:,
1722:1
1718:b
1713:(
1709:,
1705:)
1699:2
1695:a
1691:,
1686:1
1682:a
1677:(
1672:[
1668:d
1634:2
1629:)
1623:2
1619:b
1610:2
1606:a
1601:(
1596:+
1591:2
1586:)
1580:1
1576:b
1567:1
1563:a
1558:(
1551:=
1547:]
1542:)
1536:2
1532:b
1528:,
1523:1
1519:b
1514:(
1510:,
1506:)
1500:2
1496:a
1492:,
1487:1
1483:a
1478:(
1473:[
1469:d
1466:=
1461:2
1424:k
1420:P
1397:k
1393:R
1357:3
1353:R
1330:3
1326:P
1303:2
1299:R
1276:2
1272:P
1249:1
1245:R
1222:1
1218:P
1197:X
1175:k
1171:P
1148:k
1144:R
1095:K
1089:k
1085:)
1079:k
1075:R
1071:(
1045:}
1042:k
1036:j
1026:)
1021:j
1017:P
1013:,
1010:x
1007:(
1004:d
998:)
993:k
989:P
985:,
982:x
979:(
976:d
970:X
964:x
961:{
958:=
953:k
949:R
926:A
906:x
886:}
883:A
877:a
871:)
868:a
864:,
861:x
858:(
855:d
852:{
846:=
843:)
840:A
836:,
833:x
830:(
827:d
807:k
787:j
765:j
761:P
738:k
734:P
713:X
691:k
687:P
664:k
660:R
639:X
609:K
603:k
599:)
593:k
589:P
585:(
565:K
545:d
521:X
477:1
471:n
449:k
445:R
422:k
418:p
412:j
408:p
377:j
373:p
350:k
346:p
323:j
319:p
296:j
292:p
269:k
265:p
242:k
238:p
215:k
211:R
188:k
184:p
159:}
154:n
150:p
143:,
138:1
134:p
130:{
27:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
