Convex Hulls Under Uncertainty

Pankaj K. Agarwal, Sariel Har-Peled, Subhash Suri, Hakan Yıldız, Wuzhou Zhang

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)340-367
Number of pages28
JournalAlgorithmica
Volume79
Issue number2
DOIs
StatePublished - Oct 1 2017

Keywords

  • Convex hull
  • Membership probability
  • Tukey depth
  • Uncertainty

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Fingerprint Dive into the research topics of 'Convex Hulls Under Uncertainty'. Together they form a unique fingerprint.

  • Cite this

    Agarwal, P. K., Har-Peled, S., Suri, S., Yıldız, H., & Zhang, W. (2017). Convex Hulls Under Uncertainty. Algorithmica, 79(2), 340-367. https://doi.org/10.1007/s00453-016-0195-y