Guaranteed Voronoi Diagrams of Uncertain Sites

ID
TR-2008-17
Authors
William Evans and Jeff Sember
Publishing date
December 31, 2008
Length
13 pages
Abstract
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 examine the diagram for sites with disc-shaped regions of uncertainty, prove that it has linear complexity, and provide an optimal algorithm for its construction. We also show that the diagram for uncertain polygons has linear complexity. We then describe two generalizations of these diagrams for uncertain discs. In the first, which is related to a standard order-k Voronoi diagram, each cell is associated with a subset of k sites, and each point within the cell is guaranteed closer to any of the sites within the subset than to any site not in the subset. In the second, each cell is associated with the smallest subset guaranteed to contain the nearest site to each point in the cell. For both generalizations, we provide tight complexity bounds and efficient construction algorithms. Finally, we examine the Delaunay triangulations that can exist for sites within uncertain discs, and provide an optimal algorithm for generating those edges that are guaranteed to exist in every such triangulation.