Editing Voronoi diagram (section)

==Generalizations and variations==
As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean, such as the [[Mahalanobis distance]] or [[Manhattan distance]]. However, in these cases the boundaries of the Voronoi cells may be more complicated than in the Euclidean case, since the equidistant locus for two points may fail to be subspace of codimension 1, even in the two-dimensional case.

[[Image:Approximate Voronoi Diagram.svg|thumb|Approximate Voronoi diagram of a set of points. Notice the blended colors in the fuzzy boundary of the Voronoi cells.]]
A [[weighted Voronoi diagram]] is the one in which the function of a pair of points to define a Voronoi cell is a distance function modified by multiplicative or additive weights assigned to generator points. In contrast to the case of Voronoi cells defined using a distance which is a [[metric (mathematics)|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 of a point|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.<ref>{{cite book |last=Edelsbrunner |first=Herbert |author-link=Herbert Edelsbrunner |chapter=13.6 Power Diagrams |pages=327–328 |publisher=Springer-Verlag |series=EATCS Monographs on Theoretical Computer Science |title=Algorithms in Combinatorial Geometry |volume=10 |orig-year=1987 |year=2012 |isbn=9783642615689}}</ref>

The Voronoi diagram of <math>n</math> points in <math>d</math>-dimensional space can have <math display=inline>O(n^{\lceil d/2 \rceil})</math> vertices, requiring the same bound for the amount of memory needed to store an explicit description of it. Therefore, Voronoi diagrams are often not feasible for moderate or high dimensions. A more space-efficient alternative is to use approximate Voronoi diagrams.<ref>{{cite book |chapter=Space-efficient approximate Voronoi diagrams |isbn=1581134959 |doi=10.1145/509907.510011 |title=Proceedings of the thiry-fourth annual ACM symposium on Theory of computing |first1=Sunil |last1=Sunil Arya |first2=Theocharis |last2=Malamatos |first3=David M. |last3=Mount |author3-link=David Mount |date=2002 |pages=721–730 |s2cid=1727373 }}</ref>

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 diagram]]s.