Convex hulls under uncertainty

Published

Journal Article

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. © 2014 Springer-Verlag Berlin Heidelberg.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Har-Peled, S; Suri, S; YIldIz, H; Zhang, W

Published Date

  • January 1, 2014

Published In

Volume / Issue

  • 8737 LNCS /

Start / End Page

  • 37 - 48

Electronic International Standard Serial Number (EISSN)

  • 1611-3349

International Standard Serial Number (ISSN)

  • 0302-9743

Digital Object Identifier (DOI)

  • 10.1007/978-3-662-44777-2-4

Citation Source

  • Scopus