Weighted Voronoi diagram

Short description: Generalization of Voronoi diagrams

A circular Dirichlet tessellation with randomly assigned weights

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. In the plane under the ordinary Euclidean distance, the multiplicatively weighted Voronoi diagram is also called circular Dirichlet tessellation 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.

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.

External links

• Adam Dobrin: A review of properties and variations of Voronoi diagrams