An algorithm for the dynamic construction and maintenance of Additively Weighted Voronoi diagrams

Abstract:

The ordinary point Voronoi diagram is a partition of the plane, in the way that each object (point) partitions the euclidean plane into a region, that is the locus of points which are closer from that object than from any other object (see Preparata and Shamos [7]). The Voronoi diagram has many applications in a variety of disciplines, and has been widely treated in the literature (see Okabe and al.[6] and Aurenhammer [1] for a general survey). The weighted Voronoi diagrams (multiplicatively, additively, compoundly, etc...) differ from the ordinary Voronoi diagram in the fact that the generators do not have all the same weight (see Okabe and al.[6] and Aurenhammer [1]). The definition of these weighted Voronoi diagrams differs from the definition of the ordinary one in the fact that the Euclidean distance is replaced by a weighted distance. In the case of the additively weighted Voronoi diagram, the weighted distance between a point and a generator, is the Euclidean distance minus the weight of the generator. The additively weighted Voronoi diagram has been extensively studied by Ash and Bolker, under the name of hyperbolic Dirich-let tessellations (see section 2 of [3]). Up to date, only static algorithms have been developped for constructing the additively weighted Voronoi diagram. In this paper, we introduce a new algorithm (see Aurenhammer [2]) for the dynamic construction and maintenance of additively weighted Voronoi diagrams. We will illustrate the link of our algorithm with the Appolonius problem, and we will use some of the properties of the hyperbolic Dirichlet tessellations.

Año de publicación:

1998

Keywords:

Fuente:

google