Weighted Voronoi diagram

In mathematics, a weighted Voronoi diagram in n dimensions is a special case 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. Usually, the distance function is a function of the generator points' weights.

The multiplicatively weighted Voronoi diagram is defined when the distance between points is multiplied by positive weights.[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 arc 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.

The additively weighted Voronoi diagram is defined when positive weights are subtracted from the distances between points. In the plane under the ordinary Euclidean distance this diagram is also known as the hyperbolic Dirichlet tessellation and its edges are hyperbolic arc and straight line segments.[1]

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

References

  1. 1 2 "Dictionary of distances", by Elena Deza and Michel Deza pp. 255, 256
  2. ↑ Peter F. Ash1 and Ethan D. Bolker, [Generalized Dirichlet tessellations http://www.springerlink.com/content/j334537p07370405/], 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.