In mathematics, a weighted Voronoi diagram in ''n'' dimensions is a generalization of a

Voronoi diagram In mathematics, a Voronoi diagram is a partition of a plane into regions close to each of a given set of objects. In the simplest case, these objects are just finitely many points in the plane (called seeds, sites, or generators). For each seed th ...

. 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 In mathematics, the Euclidean distance between two points in Euclidean space is the length of a line segment between the two points. It can be calculated from the Cartesian coordinates of the points using the Pythagorean theorem, therefor ...

, 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."Dictionary of distances", by

Elena Deza Elena Ivanovna Deza (russian: Елена Ивановна Деза, née Panteleeva; born 23 August 1961) is a French and Russian mathematician known for her books on metric spaces and figurate numbers. Education and career Deza was born on 23 A ...

and

Michel Deza Michel Marie Deza (27 April 1939. – 23 November 2016) was a Soviet and French mathematician, specializing in combinatorics, discrete geometry and graph theory. He was the retired director of research at the French National Centre for Scien ...

br>pp. 255, 256
/ref> In the plane under the ordinary

, 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 A crystal is a solid material whose constituent atoms, molecules, or ions are arranged in an orderly repeating pattern extending in all three spatial dimensions. Crystal growth is a major stage of a crystallization process, and consists of the a ...

, 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

this diagram is also known as the hyperbolic Dirichlet tessellation and its edges are arcs of hyperbolas and straight line segments. The

power diagram In computational geometry, a power diagram, also called a Laguerre–Voronoi diagram, Dirichlet cell complex, radical Voronoi tesselation or a sectional Dirichlet tesselation, is a partition of the Euclidean plane into polygonal cells defined from ...

is defined when weights are subtracted from the squared Euclidean distance. It can also be defined using the

power distance Power distance is a dimension theorized and proven by Geert Hofstede, who outlined multiple cultural dimensions throughout his work. This term refers to inequality and unequal distributions of power between parties; whether it is within the work ...

defined from a set of circles..

References

{{reflist

External links

Adam Dobrin: A review of properties and variations of Voronoi diagrams
Discrete geometry Geometric algorithms Diagrams