@article{4125,
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.},
author = {Aurenhammer,Franz and Herbert Edelsbrunner},
journal = {Pattern Recognition},
number = {2},
pages = {251 -- 257},
publisher = {Springer},
title = {{An optimal algorithm for constructing the weighted Voronoi diagram in the plane}},
doi = {10.1016/0031-3203(84)90064-5},
volume = {17},
year = {1984},
}