On the Complexity of Randomly Weighted Voronoi Diagrams
Sariel Har-Peled,
and
Benjamin Raichel.
In this paper, we provide an $O(n \mathrm{polylog} n)$ bound on
the expected complexity of the randomly weighted Voronoi diagram
of a set of $n$ sites in the plane, where the sites can be either
points, interior-disjoint convex sets, or other more
general objects. Here the randomness is on the weight of the
sites, not their location. This compares favorably with the worst
case complexity of these diagrams, which is quadratic. As a
consequence we get an alternative proof to that of Agarwal \etal
[AHK13] of the near linear complexity of the union of
randomly expanded disjoint segments or convex sets (with an
improved bound on the latter). The technique we develop is
elegant and should be applicable to other problems.
PDF.
Last modified: Wed Jan 22 16:16:07 CST 2014