Weighted Voronoi diagram

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In mathematics, a weighted Voronoi diagram in n dimensions is a Voronoi diagram for which the Voronoi cells are defined in terms of a distance defined by some common metrics modified by weights assigned to generator points.

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]


  1. ^ a b "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 .

External links[edit]