An optimal algorithm for constructing the weighted Voronoi diagram in the plane (Q793982)

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 defined as \(d(x,z)^ 2-r^ 2.)\) Such diagrams can be constructed as well in \(0(n^ 2)\) time by projecting the boundaries of convex polyhedra in four dimensions.