article
An optimal algorithm for constructing the weighted Voronoi diagram in the plane
published
Franz
Aurenhammer
author
Herbert
Edelsbrunner
author 3FB178DA-F248-11E8-B48F-1D18A9856A870000-0002-9823-6833
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.
Springer1984
Pattern Recognition10.1016/0031-3203(84)90064-5
172251 - 257
yes
Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>. Springer, 1984. <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>.
Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.” <i>Pattern Recognition</i>, vol. 17, no. 2, Springer, 1984, pp. 251–57, doi:<a href="https://doi.org/10.1016/0031-3203(84)90064-5">10.1016/0031-3203(84)90064-5</a>.
F. Aurenhammer and H. Edelsbrunner, “An optimal algorithm for constructing the weighted Voronoi diagram in the plane,” <i>Pattern Recognition</i>, vol. 17, no. 2. Springer, pp. 251–257, 1984.
F. Aurenhammer, H. Edelsbrunner, Pattern Recognition 17 (1984) 251–257.
Aurenhammer F, Edelsbrunner H. 1984. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.
Aurenhammer, F., & Edelsbrunner, H. (1984). An optimal algorithm for constructing the weighted Voronoi diagram in the plane. <i>Pattern Recognition</i>. Springer. <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>
Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. <i>Pattern Recognition</i>. 1984;17(2):251-257. doi:<a href="https://doi.org/10.1016/0031-3203(84)90064-5">10.1016/0031-3203(84)90064-5</a>
41252018-12-11T12:07:05Z2021-01-12T07:54:41Z