DOI 10.1007/s00778-012-0290-x REGULAR PAPER UV-diagram: a voronoi diagram for uncertain spatial databases

© The Author(s) 2012. This article is published with open access at Springerlink.com Abstract The Voronoi diagram is an important technique for answering nearest-neighbor queries for spatial databases. We study how the Voronoi diagram can be used for uncer-tain spatial data, which are inherent in scientific and business applications. Specifically, we propose the Uncertain-Voronoi diagram (or UV-diagram), which divides the data space into disjoint “UV-partitions”. Each UV-partition P is associated with a set S of objects, such that any point q located in P has the set S as its nearest neighbor with nonzero proba-bilities. The UV-diagram enables queries that return objects with nonzero chances of being the nearest neighbor (NN) of a given point q. It supports “continuous nearest-neighbor search”, which refreshes the set of NN objects of q, as the position of q changes. It also allows the analysis of nearest-neighbor information, for example, to find out the numbe