TY - GEN
T1 - Convex hulls under uncertainty
AU - Agarwal, Pankaj K.
AU - Har-Peled, Sariel
AU - Suri, Subhash
AU - YIldIz, Hakan
AU - Zhang, Wuzhou
PY - 2014
Y1 - 2014
N2 - 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 point is described by a probability distribution over a finite number of possible locations including a 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 β-hull that may be a useful representation of uncertain hulls.
AB - 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 point is described by a probability distribution over a finite number of possible locations including a 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 β-hull that may be a useful representation of uncertain hulls.
UR - http://www.scopus.com/inward/record.url?scp=84958537614&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84958537614&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-44777-2_4
DO - 10.1007/978-3-662-44777-2_4
M3 - Conference contribution
AN - SCOPUS:84958537614
SN - 9783662447765
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 37
EP - 48
BT - Algorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PB - Springer
T2 - 22nd Annual European Symposium on Algorithms, ESA 2014
Y2 - 8 September 2014 through 10 September 2014
ER -