Convex Hulls under Uncertainty

Creative Commons License

Agarwal P. K., Har-Peled S., Suri S., Yildiz H., Zhang W.

22nd Annual European Symposium on Algorithms (ESA) held as part of ALGO Meeting, Wroclaw, Poland, 8 - 10 September 2014, vol.8737, pp.37-48 identifier identifier

  • Publication Type: Conference Paper / Full Text
  • Volume: 8737
  • Doi Number: 10.1007/978-3-662-44777-2_4
  • City: Wroclaw
  • Country: Poland
  • Page Numbers: pp.37-48
  • Middle East Technical University Affiliated: No


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 beta-hull that may be a useful representation of uncertain hulls.