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