Convex Hulls Under Uncertainty

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

Research output: Contribution to journalArticlepeer-review

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

  • General Computer Science
  • Computer Science Applications
  • Applied Mathematics

Fingerprint

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

Cite this