An optimal algorithm for constructing the weighted Voronoi diagram in
F. Aurenhammer and H. Edelsbrunner
denote a set of
points in the plane such that each point
assigned a positive weight
which expresses its capability to influence
its neighborhood. In this sense, the weighted distance of an arbitrary point
is gived by
denotes the Euclidean
distance function. The weighted Voronoi diagram for
is a subdivision of
the plane such that each point
is associated with a region
consisting of all points
in the plane for which
is a weighted nearest
. An algorithm which constructs the weighted Voronoi diagram for
time is outlined in this paper. The method is optimal as the
diagram can consist of
faces, edges, and vertices.
Reference: F. Aurenhammer and H. Edelsbrunner.
An optimal algorithm for constructing the weighted Voronoi diagram in the
Pattern Recognition, 17(2):251-257, 1984.
[IIG-Report-Series F109, TU Graz, Austria, 1983].