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

Aurenhammer F, Edelsbrunner H. 1983. 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*|

*English*

**Scopus indexed**

Author

Aurenhammer, Franz;
Edelsbrunner, Herbert

^{ISTA}^{}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

1983-07-01

Journal Title

Pattern Recognition

Publisher

Elsevier

Acknowledgement

The second author gratefully acknowledges discussions on the presented topic with David Kirkpatrick and Raimund Seidel.

Volume

17

Issue

2

Page

251 - 257

ISSN

eISSN

IST-REx-ID

### Cite this

Aurenhammer F, Edelsbrunner H. An optimal algorithm for constructing the weighted Voronoi diagram in the plane.

*Pattern Recognition*. 1983;17(2):251-257. doi:10.1016/0031-3203(84)90064-5Aurenhammer, F., & Edelsbrunner, H. (1983). An optimal algorithm for constructing the weighted Voronoi diagram in the plane.

*Pattern Recognition*. Elsevier. 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*. Elsevier, 1983. 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. Elsevier, pp. 251–257, 1983.Aurenhammer, Franz, and Herbert Edelsbrunner. “An Optimal Algorithm for Constructing the Weighted Voronoi Diagram in the Plane.”

*Pattern Recognition*, vol. 17, no. 2, Elsevier, 1983, pp. 251–57, doi:10.1016/0031-3203(84)90064-5.**Link(s) to Main File(s)**

Access Level

Closed Access