An optimal algorithm for constructing the weighted Voronoi diagram in the plane
type: Item
instance of: scholarly article
title: An optimal algorithm for constructing the weighted Voronoi diagram in the plane
zbMATH Open document ID: 0539.52008
DOI: 10.1016/0031-3203(84)90064-5
published in: Pattern Recognition
publication date: 1984-01-01T00:00:00Z
review text: Within the newly emerged discipline of computer science called computational geometry, the Voronoi diagram of a finite set S of points in the xy-plane, \(h_ 0\), plays an important role. It associates each \(p\in S\) with the convex region \(reg(p)=\{x\in h_ o | d(x,p)\leq d(x,q),q\in S-\{p\}\}.\) The diagram can be generalized by assigning a constant \(w(p)>0\) to each \(p\in S\) and replacing d(x,p) by d(x,p)/w(p), and is termed the weighted Voronoi diagram, WVD(S), of S. Its scope of applications includes geography, economy, and chemistry. The set \(circ(p,q)=\{x\in h_ 0 | d(x,p)/w(p)=d(x,q)/w(q),p\neq q\in S\}\) is a circle (which degenerates to a straight line for \(w(p)=w(q))\), such that WVD(S) is a partition of \(h_ 0\) with circular arcs. In contrast to the original structure, the regions of WVD(S) may be non- connected and realize \(\Omega(n^ 2)\) connected components, for \(| S| =n\). In order to design an efficient algorithm for its construction, the diagram is embedded in three dimensions. We choose a point I not in \(h_ 0\) and denote ball(p,q) the ball (resp. its complement) containing I and circ(p,q) on its boundary, and p in its interior. Let \(sreg(p)=\cap_{q\in S-\{p\}}ball(p,q).\) Then \(\{sreg(p,q)| p\in S\}\) is a spherical partition of the space, which can be mapped into a cell complex, C(S), by inversion with respect to center I. As a consequence, WVD(S) can be constructed by inverting C(S)\(\cap h'\!_ 0\), for h'\({}_ 0\) the inverted image of \(h_ 0\). The main part of the algorithm computes C(S) by incrementally inserting the weighted points. Since WVD(S) can be derived from C(S) in time proportional to the number of its arcs, this method achieves a time complexity of \(0(n^ 2)\), which is asymptotically optimal in the worst case. We mention that C(S) can be interpreted as a generalized Voronoi diagram, induced by a set of n spheres and the power function. (The power of a point x with respect to a sphere with center z and radius r is defin…
Mathematics Subject Classification ID: 52Bxx
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 3857864
zbMATH Keywords: weighted points
zbMATH Keywords: domain of influence
zbMATH Keywords: geometric transform
zbMATH Keywords: ball(p,q)
zbMATH Keywords: circ(p,q)
author: Franz Aurenhammer
author: Herbert Edelsbrunner
MaRDI profile type: Publication
full work available at URL: 0031-3203(84)90064-5
OpenAlex ID: W2001099600
cites work: Construction of Voronoi polyhedra
cites work: Q4133127
cites work: Q5547252
cites work: The one-dimensional weighted Voronoi diagram
cites work: A New Approach to Planar Point Location
description: scientific article; zbMATH DE number 3857864