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

F. Aurenhammer and H. Edelsbrunner

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 neighborhood. In this sense, the weighted distance of an arbitrary point $x$ from $p$ is gived by $d_e(x,p)/w(p)$, where $d_e$ 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(n^2)$ time is outlined in this paper. The method is optimal as the diagram can consist of $\Theta(n^2)$ faces, edges, and vertices.

Reference: F. Aurenhammer and H. Edelsbrunner. An optimal algorithm for constructing the weighted Voronoi diagram in the plane. Pattern Recognition, 17(2):251-257, 1984. [IIG-Report-Series F109, TU Graz, Austria, 1983].