In this paper we investigate the Voronoi diagram that is induced by a set of sites in the plane, where each site's precise location is uncertain but is known to be within a particular region, and the cells of this diagram contain those points guaranteed to be closest to a particular site. We then examine the diagram for sites with disc-shaped regions of uncertainty, prove that it has linear complex- ity, and provide an optimal O(nlogn) algorithm for its construction. We also examine the diagram for polygo- nal regions of uncertainty, and prove that it has linear complexity as well. We then describe a generalization of these diagrams, in which each Voronoi cell is associ- ated with a subset of the sites, and each point in a cell is guaranteed to be closest to some site in the subset associated with the cell.
['Jeff Sember', 'William S. Evans']
Guaranteed Voronoi Diagrams of Uncertain Sites