×

An optimal algorithm for constructing the weighted Voronoi diagram in the plane. (English) Zbl 0539.52008

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.

MSC:

52Bxx Polytopes and polyhedra
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Voronoi, G., Nouvelles applications des paramètres continues à la théorie des formes quadratiques, (Deuxième mémoire: recherches sur les paralléloedes primitifs. Deuxième mémoire: recherches sur les paralléloedes primitifs, J. reine angew. Math., 134 (1908)), 198-287 · JFM 39.0274.01
[2] Brostow, W.; Dussault, J.-P.; Fox, B. L., Construction of Voronoi polyhedra, J. Comput. Physics, 29, 81-92 (1978) · Zbl 0392.73097
[3] Rhynsburger, D., Analytic delineation of Thiessen polygons, Geogrl Analysis, 5, 133-144 (1973)
[4] Blum, H., Biological shape and visual science (Part I), J. theor. Biol., 38, 205-287 (1973)
[5] Bowyer, A., Computing Dirichlet tesselations, Comput. J., 24, 162-166 (1981)
[6] Hodder, I.; Orton, C., Spatial Analysis in Archeology (1976), Cambridge
[7] Shamos, M. I., Geometric complexity, (Proc. 7th Annual ACM STOC (1975)), 224-233
[8] Shamos, M. I.; Hoey, D., Closest point problems, (Proc. 16th Annual IEEE Symp. FOCS (1975)), 151-162
[9] Seidel, R., A convex hull algorithm optimal for point sets in even dimensions, (M.Sc. Thesis, Report 81-14, Department of Computer Science (1981), University of British Columbia: University of British Columbia Vancouver)
[10] Brown, K. Q., Geometric transforms for fast geometric algorithms, (Ph.D. Thesis, Report CMU-CS-80-101, Department of Computer Science (1980), Carnegie-Mellon University: Carnegie-Mellon University Pittsburgh, Pennsylvania)
[11] Drysdale, R. L.; Lee, D. T., Generalized Voronoi diagrams and geometric searching, (Proc. 16th Annual Allerton Conf. on Communications, Control and Computers (1978)), 833-842
[12] Kirkpatrick, D. G., Efficient computation of continuous skeletons, (Proc. 20th Annual IEEE Symp. EOCS (1979)), 18-27
[13] Boots, B. N., Weighting Thiessen polygons, Econ. Geogr., 248-259 (1979)
[14] Gambini, R.; Huff, D. L.; Jenks, G. F., Geometric properties of market areas, Pap. Reg. Sci. Ass., 20, 85-92 (1967)
[15] Huff, D. L.; Jenks, G. F., A graphic interpretation of the friction of distance in gravity models, Ann. Ass. Am. Geogr., 58, 814-824 (1968)
[16] Huff, D. L., The delineation of a national system of planning regions on the basis of urban spheres of influence, Reg. Studies, 7, 323-329 (1973)
[17] A. A. Schoone and J. van Leeuwen, Private communication (1982).; A. A. Schoone and J. van Leeuwen, Private communication (1982).
[18] Gruenbaum, B., Convex Polytopes (1967), Wiley Interscience
[19] Aurenhammer, F., The one-dimensional weighted Voronoi diagram, (Report, F110 (1982), Institutes for Information Processing, Technical University of Graz: Institutes for Information Processing, Technical University of Graz Austria) · Zbl 0586.68036
[20] Preparata, F. P., A new approach to planar point location, SIAM J. Comput., 10, 473-482 (1981) · Zbl 0462.68048
[21] Seidel, R., On the size of closest point Voronoi diagrams, (Report, F94 (1982), Institutes for Information Processing, Technical University of Graz: Institutes for Information Processing, Technical University of Graz Austria)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.