Voronoi Diagram - Generalizations and Variations

Generalizations and Variations

As implied by the definition, Voronoi cells can be defined for metrics other than Euclidean (such as the Mahalanobis or Manhattan) distances. 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 2-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 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 distance from the circle's center.

The Voronoi diagram of n points in d-dimensional space requires storage space. Therefore, Voronoi diagrams are often not feasible for d > 2. An alternative is to use approximate Voronoi diagrams, where the Voronoi cells have a fuzzy boundary, which can be approximated. Another alternative is when any site is a fuzzy circle and as a result the cells become fuzzy too.

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