The dodecahedral conjecture in geometry is intimately related to sphere packing .
36-466: László Fejes Tóth , a 20th-century Hungarian geometer, considered the Voronoi decomposition of any given packing of unit spheres . He conjectured in 1943 that the minimal volume of any cell in the resulting Voronoi decomposition was at least as large as the volume of a regular dodecahedron circumscribed to a unit sphere. Thomas Callister Hales and Sean McLaughlin proved the conjecture in 1998, following
72-410: A half-space is either of the two parts into which a plane divides the three-dimensional Euclidean space . If the space is two-dimensional , then a half-space is called a half-plane (open or closed). A half-space in a one-dimensional space is called a half-line or ray . More generally, a half-space is either of the two parts into which a hyperplane divides an affine space . That is,
108-415: A Voronoi diagram generated on the set S − X . For a set of n points the ( n − 1) -order Voronoi diagram is called a farthest-point Voronoi diagram. For a given set of points S = { p 1 , p 2 , ..., p n } the farthest-point Voronoi diagram divides the plane into cells in which the same point of P is the farthest point. A point of P has
144-545: A cell in the farthest-point Voronoi diagram if and only if it is a vertex of the convex hull of P . Let H = { h 1 , h 2 , ..., h k } be the convex hull of P ; then the farthest-point Voronoi diagram is a subdivision of the plane into k cells, one for each point in H , with the property that a point q lies in the cell corresponding to a site h i if and only if d( q , h i ) > d( q , p j ) for each p j ∈ S with h i ≠ p j , where d( p , q )
180-449: A given set of objects. It can be classified also as a tessellation . In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed there is a corresponding region , called a Voronoi cell , consisting of all points of the plane closer to that seed than to any other. The Voronoi diagram of a set of points is dual to that set's Delaunay triangulation . The Voronoi diagram
216-405: A particular set of n points in S as its n nearest neighbors. Higher-order Voronoi diagrams also subdivide space. Higher-order Voronoi diagrams can be generated recursively. To generate the n -order Voronoi diagram from set S , start with the ( n − 1) -order diagram and replace each cell generated by X = { x 1 , x 2 , ..., x n −1 } with
252-448: A point that generates its Voronoi region R 1 {\textstyle R_{1}} , P 2 {\textstyle P_{2}} that generates R 2 {\textstyle R_{2}} , and P 3 {\textstyle P_{3}} that generates R 3 {\textstyle R_{3}} , and so on. Then, as expressed by Tran et al , "all locations in
288-541: A set of seed points, and steps in which the seed points are moved to new locations that are more central within their cells. These methods can be used in spaces of arbitrary dimension to iteratively converge towards a specialized form of the Voronoi diagram, called a Centroidal Voronoi tessellation , where the sites have been moved to points that are also the geometric centers of their cells. Voronoi meshes can also be generated in 3D. Half-space (geometry) In geometry ,
324-403: A tessellation of space with rhombo-hexagonal dodecahedra . For the set of points ( x , y ) with x in a discrete set X and y in a discrete set Y , we get rectangular tiles with the points not necessarily at their centers. Although a normal Voronoi cell is defined as the set of points closest to a single point in S , an n th-order Voronoi cell is defined as the set of points having
360-412: Is known as influence area of the station. The average precipitation is calculated by the formula P ¯ = ∑ A i P i ∑ A i {\displaystyle {\bar {P}}={\frac {\sum A_{i}P_{i}}{\sum A_{i}}}} Several efficient algorithms are known for constructing Voronoi diagrams, either directly (as
396-445: Is named after mathematician Georgy Voronoy , and is also called a Voronoi tessellation , a Voronoi decomposition , a Voronoi partition , or a Dirichlet tessellation (after Peter Gustav Lejeune Dirichlet ). Voronoi cells are also known as Thiessen polygons , after Alfred H. Thiessen . Voronoi diagrams have practical and theoretical applications in many fields, mainly in science and technology , but also in visual art . In
SECTION 10
#1733117145631432-578: Is simply the tuple of cells ( R k ) k ∈ K {\textstyle (R_{k})_{k\in K}} . In principle, some of the sites can intersect and even coincide (an application is described below for sites representing shops), but usually they are assumed to be disjoint. In addition, infinitely many sites are allowed in the definition (this setting has applications in geometry of numbers and crystallography ), but again, in many cases only finitely many sites are considered. In
468-471: Is the Euclidean distance between two points p and q . The boundaries of the cells in the farthest-point Voronoi diagram have the structure of a topological tree , with infinite rays as its leaves. Every finite tree is isomorphic to the tree formed in this way from a farthest-point Voronoi diagram. As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean, such as
504-419: Is the intersection of all of these n − 1 {\displaystyle n-1} half-spaces, and hence it is a convex polygon . When two cells in the Voronoi diagram share a boundary, it is a line segment , ray , or line, consisting of all the points in the plane that are equidistant to their two nearest sites. The vertices of the diagram, where three or more of these boundaries meet, are
540-429: Is the union of an open half-space and the hyperplane that defines it. The open (closed) upper half-space is the half-space of all ( x 1 , x 2 , ..., x n ) such that x n > 0 (≥ 0). The open (closed) lower half-space is defined similarly, by requiring that x n be negative (non-positive). A half-space may be specified by a linear inequality, derived from the linear equation that specifies
576-462: 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 results in the formation of polygons around the stations. The area ( A i ) {\displaystyle (A_{i})} touching station point
612-611: The Mahalanobis distance or Manhattan distance . However, in these cases the boundaries of the Voronoi cells may be more complicated than in the Euclidean case, since the equidistant locus for two points may fail to be subspace of codimension 1, even in the two-dimensional case. A weighted Voronoi diagram is the one in which the function of a pair of points to define a Voronoi cell is a distance function modified by multiplicative or additive weights assigned to generator points. In contrast to
648-403: The Euclidean plane for which p k {\displaystyle p_{k}} is the nearest site: the distance to p k {\displaystyle p_{k}} is less than or equal to the minimum distance to any other site p j {\displaystyle p_{j}} . For one other site p j {\displaystyle p_{j}} ,
684-483: The Voronoi cells may not be convex or even connected. In the usual Euclidean space, we can rewrite the formal definition in usual terms. Each Voronoi polygon R k {\textstyle R_{k}} is associated with a generator point P k {\textstyle P_{k}} . Let X {\textstyle X} be the set of all points in the Euclidean space. Let P 1 {\textstyle P_{1}} be
720-474: The Voronoi diagram. The Jump Flooding Algorithm can generate approximate Voronoi diagrams in constant time and is suited for use on commodity graphics hardware. Lloyd's algorithm and its generalization via the Linde–Buzo–Gray algorithm (aka k-means clustering ) use the construction of Voronoi diagrams as a subroutine. These methods alternate between steps in which one constructs the Voronoi diagram for
756-470: The Voronoi polygon are closer to the generator point of that polygon than any other generator point in the Voronoi diagram in Euclidean plane". As a simple illustration, consider a group of shops in a city. Suppose we want to estimate the number of customers of a given shop. With all else being equal (price, products, quality of service, etc.), it is reasonable to assume that customers choose their preferred shop simply by distance considerations: they will go to
SECTION 20
#1733117145631792-722: The case of Voronoi cells defined using a distance which is a metric , in this case some of the Voronoi cells may be empty. A power diagram is a type of Voronoi diagram defined from a set of circles using the power distance ; it can also be thought of as a weighted Voronoi diagram in which a weight defined from the radius of each circle is added to the squared Euclidean distance from the circle's center. The Voronoi diagram of n {\displaystyle n} points in d {\displaystyle d} -dimensional space can have O ( n ⌈ d / 2 ⌉ ) {\textstyle O(n^{\lceil d/2\rceil })} vertices, requiring
828-433: The diagram itself) or indirectly by starting with a Delaunay triangulation and then obtaining its dual. Direct algorithms include Fortune's algorithm , an O ( n log( n )) algorithm for generating a Voronoi diagram from a set of points in a plane. Bowyer–Watson algorithm , an O ( n log( n )) to O ( n ) algorithm for generating a Delaunay triangulation in any number of dimensions, can be used in an indirect algorithm for
864-532: The distance between the point x {\textstyle x} and the subset A {\textstyle A} , then R k = { x ∈ X ∣ d ( x , P k ) ≤ d ( x , P j ) for all j ≠ k } {\displaystyle R_{k}=\{x\in X\mid d(x,P_{k})\leq d(x,P_{j})\;{\text{for all}}\;j\neq k\}} The Voronoi diagram
900-497: The familiar Euclidean distance : or the Manhattan distance : The corresponding Voronoi diagrams look different for different distance metrics. Informal use of Voronoi diagrams can be traced back to Descartes in 1644. Peter Gustav Lejeune Dirichlet used two-dimensional and three-dimensional Voronoi diagrams in his study of quadratic forms in 1850. British physician John Snow used a Voronoi-like diagram in 1854 to illustrate how
936-979: The majority of people who died in the Broad Street cholera outbreak lived closer to the infected Broad Street pump than to any other water pump. Voronoi diagrams are named after Georgy Feodosievych Voronoy who defined and studied the general n -dimensional case in 1908. Voronoi diagrams that are used in geophysics and meteorology to analyse spatially distributed data are called Thiessen polygons after American meteorologist Alfred H. Thiessen , 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). Voronoi tessellations of regular lattices of points in two or three dimensions give rise to many familiar tessellations. Certain body-centered tetragonal lattices give
972-463: The other sites P j {\textstyle P_{j}} , where j {\textstyle j} is any index different from k {\textstyle k} . In other words, if d ( x , A ) = inf { d ( x , a ) ∣ a ∈ A } {\textstyle d(x,\,A)=\inf\{d(x,\,a)\mid a\in A\}} denotes
1008-423: The particular case where the space is a finite-dimensional Euclidean space , each site is a point, there are finitely many points and all of them are different, then the Voronoi cells are convex polytopes and they can be represented in a combinatorial way using their vertices, sides, two-dimensional faces, etc. Sometimes the induced combinatorial structure is referred to as the Voronoi diagram. In general however,
1044-422: The points that are closer to p k {\displaystyle p_{k}} than to p j {\displaystyle p_{j}} , or equally distant, form a closed half-space , whose boundary is the perpendicular bisector of line segment p j p k {\displaystyle p_{j}p_{k}} . Cell R k {\displaystyle R_{k}}
1080-411: The points that are not incident to the hyperplane are partitioned into two convex sets (i.e., half-spaces), such that any subspace connecting a point in one set to a point in the other must intersect the hyperplane. A half-space can be either open or closed . An open half-space is either of the two open sets produced by the subtraction of a hyperplane from the affine space. A closed half-space
1116-459: The points that have three or more equally distant nearest sites. Let X {\textstyle X} be a metric space with distance function d {\textstyle d} . Let K {\textstyle K} be a set of indices and let ( P k ) k ∈ K {\textstyle (P_{k})_{k\in K}} be a tuple (indexed collection) of nonempty subsets (the sites) in
Dodecahedral conjecture - Misplaced Pages Continue
1152-513: The same bound for the amount of memory needed to store an explicit description of it. Therefore, Voronoi diagrams are often not feasible for moderate or high dimensions. A more space-efficient alternative is to use approximate Voronoi diagrams . Voronoi diagrams are also related to other geometric structures such as the medial axis (which has found applications in image segmentation, optical character recognition , and other computational applications), straight skeleton , and zone diagrams . It
1188-474: The same strategy that led Hales to his proof of the Kepler conjecture . The proofs rely on extensive computations. McLaughlin was awarded the 1999 Morgan Prize for his contribution to this proof. This geometry-related article is a stub . You can help Misplaced Pages by expanding it . Voronoi decomposition In mathematics , a Voronoi diagram is a partition of a plane into regions close to each of
1224-413: The shop located nearest to them. In this case the Voronoi cell R k {\displaystyle R_{k}} of a given shop P k {\displaystyle P_{k}} can be used for giving a rough estimate on the number of potential customers going to this shop (which is modeled by a point in our city). For most cities, the distance between points can be measured using
1260-474: The simplest case, shown in the first picture, we are given a finite set of points { p 1 , … p n } {\displaystyle \{p_{1},\dots p_{n}\}} in the Euclidean plane . In this case each site p k {\displaystyle p_{k}} is one of these given points, and its corresponding Voronoi cell R k {\displaystyle R_{k}} consists of every point in
1296-424: The space X {\textstyle X} . The Voronoi cell, or Voronoi region, R k {\textstyle R_{k}} , associated with the site P k {\textstyle P_{k}} is the set of all points in X {\textstyle X} whose distance to P k {\textstyle P_{k}} is not greater than their distance to
#630369