Weighted Voronoi diagram

In mathematics, a weighted Voronoi diagram in n dimensions is a generalization of a Voronoi diagram. The Voronoi cells in a weighted Voronoi diagram are defined in terms of a distance function. The distance function may specify the usual Euclidean distance, or may be some other, special distance function. In weighted Voronoi diagrams, each site has a weight that influences the distance computation. The idea is that larger weights indicate more important sites, and such sites will get bigger Voronoi cells.

In a multiplicatively weighted Voronoi diagram, the distance between a point and a site is divided by the (positive) weight of the site.[1] In the plane under the ordinary Euclidean distance, the multiplicatively weighted Voronoi diagram is also called circular Dirichlet tessellation[2][3] and its edges are circular arcs and straight line segments. A Voronoi cell may be non-convex, disconnected and may have holes. This diagram arises, e.g., as a model of crystal growth, where crystals from different points may grow with different speed. Since crystals may grow in empty space only and are continuous objects, a natural variation is the crystal Voronoi diagram, in which the cells are defined somewhat differently.

In an additively weighted Voronoi diagram, weights are subtracted from the distances. In the plane under the ordinary Euclidean distance this diagram is also known as the hyperbolic Dirichlet tessellation and its edges are arcs of hyperbolas and straight line segments.[1]

The power diagram is defined when weights are subtracted from the squared Euclidean distance. It can also be defined using the power distance defined from a set of circles.[4]

References
  1. "Dictionary of distances", by Elena Deza and Michel Deza pp. 255, 256
  2. Peter F. Ash and Ethan D. Bolker, [Generalized Dirichlet tessellations https://doi.org/10.1007%2FBF00164401], Geometriae Dedicata, Volume 20, Number 2 , 209-243doi:10.1007/BF00164401
  3. Note: "Dirichlet tessellation" is a synonym for "Voronoi diagram".
  4. Edelsbrunner, Herbert (1987), "13.6 Power Diagrams", Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, 10, Springer-Verlag, pp. 327–328.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.