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.
A circular Dirichlet tessellation with randomly assigned weights
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]
^Edelsbrunner, Herbert (1987), "13.6 Power Diagrams", Algorithms in Combinatorial Geometry, EATCS Monographs on Theoretical Computer Science, vol. 10, Springer-Verlag, pp. 327–328.
External linksedit
Adam Dobrin: A review of properties and variations of Voronoi diagrams
April 11, 2024
weighted, voronoi, diagram, mathematics, weighted, voronoi, diagram, dimensions, generalization, voronoi, diagram, voronoi, cells, weighted, voronoi, diagram, defined, terms, distance, function, distance, function, specify, usual, euclidean, distance, some, ot. 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 A circular Dirichlet tessellation with randomly assigned weightsIn 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 edit a b Dictionary of distances by Elena Deza and Michel Deza pp 255 256 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 Note Dirichlet tessellation is a synonym for Voronoi diagram Edelsbrunner Herbert 1987 13 6 Power Diagrams Algorithms in Combinatorial Geometry EATCS Monographs on Theoretical Computer Science vol 10 Springer Verlag pp 327 328 External links editAdam Dobrin A review of properties and variations of Voronoi diagrams Retrieved from https en wikipedia org w index php title Weighted Voronoi diagram amp oldid 1205102166, wikipedia, wiki, book, books, library,
