Convex hulls under uncertainty

Pankaj K. Agarwal, Sariel Har-Peled, Subhash Suri, Hakan YIldIz, Wuzhou Zhang

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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)
Title of host publicationAlgorithms, ESA 2014 - 22nd Annual European Symposium, Proceedings
PublisherSpringer
Pages37-48
Number of pages12
ISBN (Print)9783662447765
DOIs
StatePublished - 2014
Event22nd Annual European Symposium on Algorithms, ESA 2014 - Wroclaw, Poland
Duration: Sep 8 2014Sep 10 2014

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8737 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other22nd Annual European Symposium on Algorithms, ESA 2014
Country/TerritoryPoland
CityWroclaw
Period9/8/149/10/14

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Convex hulls under uncertainty'. Together they form a unique fingerprint.

Cite this