An optimal algorithm for constructing the weighted Voronoi diagram in the plane

F. Aurenhammer, H. Edelsbrunner, Pattern Recognition 17 (1984) 251–257.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
;
Abstract
Let S denote a set of n points in the plane such that each point p has assigned a positive weight w(p) which expresses its capability to influence its neighbourhood. In this sense, the weighted distance of an arbitrary point x from p is given by de(x,p)/w(p) where de denotes the Euclidean distance function. The weighted Voronoi diagram for S is a subdivision of the plane such that each point p in S is associated with a region consisting of all points x in the plane for which p is a weighted nearest point of S. An algorithm which constructs the weighted Voronoi diagram for S in O(n2) time is outlined in this paper. The method is optimal as the diagram can consist of Θ(n2) faces, edges and vertices.
Publishing Year
Date Published
1984-01-01
Journal Title
Pattern Recognition
Volume
17
Issue
2
Page
251 - 257
IST-REx-ID

Cite this

Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition. 1984;17(2):251-257. doi:10.1016/0031-3203(84)90064-5
Aurenhammer, F., & Edelsbrunner, H. (1984). An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 17(2), 251–257. https://doi.org/10.1016/0031-3203(84)90064-5
Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.” Pattern Recognition 17, no. 2 (1984): 251–57. https://doi.org/10.1016/0031-3203(84)90064-5.
F. Aurenhammer and H. Edelsbrunner, “An optimal algorithm for constructing the weighted Voronoi diagram in the plane,” Pattern Recognition, vol. 17, no. 2, pp. 251–257, 1984.
Aurenhammer F, Edelsbrunner H. 1984. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.
Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.” Pattern Recognition, vol. 17, no. 2, Springer, 1984, pp. 251–57, doi:10.1016/0031-3203(84)90064-5.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar