%0 Journal Article
%T Convex Hulls under Uncertainty
%A Pankaj K. Agarwal
%A Sariel Har-Peled
%A Subhash Suri
%A Hakan Yildiz
%A Wuzhou Zhang
%J Computer Science
%D 2014
%I arXiv
%X We study the convex-hull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, location-based services and computer vision. In our framework, the uncertainty of each input site is described by a probability distribution over a finite number of possible locations including a \emph{null} location to account for non-existence of the point. Our results include both exact and approximation algorithms for computing the probability of a query point lying inside the convex hull of the input, time-space tradeoffs for the membership queries, a connection between Tukey depth and membership queries, as well as a new notion of $\some$-hull that may be a useful representation of uncertain hulls.
%U http://arxiv.org/abs/1406.6599v1