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> 17, no. 2 (1984): 251–57. <a href="https://doi.org/10.1016/0031-3203(84)90064-5">https://doi.org/10.1016/0031-3203(84)90064-5</a>.
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. <i>Pattern Recognition</i>, <i>17</i>(2), 251–257. <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>
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.” <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, pp. 251–257, 1984.
41252018-12-11T12:07:05Z2019-04-26T07:22:41Z