---
_id: '4125'
abstract:
- lang: eng
text: |-
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.
author:
- first_name: Franz
full_name: Aurenhammer,Franz
last_name: Aurenhammer
- first_name: Herbert
full_name: Herbert Edelsbrunner
id: 3FB178DA-F248-11E8-B48F-1D18A9856A87
last_name: Edelsbrunner
orcid: 0000-0002-9823-6833
citation:
ama: 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
apa: 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
chicago: '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.'
ieee: 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.
ista: Aurenhammer F, Edelsbrunner H. 1984. An optimal algorithm for constructing
the weighted Voronoi diagram in the plane. Pattern Recognition. 17(2), 251–257.
mla: 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.
short: F. Aurenhammer, H. Edelsbrunner, Pattern Recognition 17 (1984) 251–257.
date_created: 2018-12-11T12:07:05Z
date_published: 1984-01-01T00:00:00Z
date_updated: 2019-04-26T07:22:41Z
day: '01'
doi: 10.1016/0031-3203(84)90064-5
extern: 1
intvolume: ' 17'
issue: '2'
month: '01'
page: 251 - 257
publication: Pattern Recognition
publication_status: published
publisher: Springer
publist_id: '1997'
quality_controlled: 0
status: public
title: An optimal algorithm for constructing the weighted Voronoi diagram in the plane
type: journal_article
volume: 17
year: '1984'
...