**F. Aurenhammer and H. Edelsbrunner**

Let denote a set of points in the plane such that each point has
assigned a positive weight which expresses its capability to influence
its neighborhood. In this sense, the weighted distance of an arbitrary point
from is gived by , where denotes the Euclidean
distance function. The weighted Voronoi diagram for is a subdivision of
the plane such that each point in is associated with a region
consisting of all points in the plane for which is a weighted nearest
point of . An algorithm which constructs the weighted Voronoi diagram for
in time is outlined in this paper. The method is optimal as the
diagram can consist of faces, edges, and vertices.