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

Aurenhammer F, Edelsbrunner H. 1984. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.

Download

**No fulltext has been uploaded. References only!**

*Journal Article*|

*Published*

Author

Aurenhammer,Franz;
Edelsbrunner, Herbert

^{IST Austria}^{}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-5Aurenhammer, F., & Edelsbrunner, H. (1984). An optimal algorithm for constructing the weighted Voronoi diagram in the plane.

*Pattern Recognition*. Springer. https://doi.org/10.1016/0031-3203(84)90064-5Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.”

*Pattern Recognition*. Springer, 1984. 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. Springer, pp. 251–257, 1984.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.