Convex Hulls Under Uncertainty

Creative Commons License

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

ALGORITHMICA, cilt.79, sa.2, ss.340-367, 2017 (SCI-Expanded) identifier identifier

  • Yayın Türü: Makale / Tam Makale
  • Cilt numarası: 79 Sayı: 2
  • Basım Tarihi: 2017
  • Doi Numarası: 10.1007/s00453-016-0195-y
  • Dergi Adı: ALGORITHMICA
  • Derginin Tarandığı İndeksler: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Sayfa Sayıları: ss.340-367
  • Anahtar Kelimeler: Convex hull, Membership probability, Tukey depth, Uncertainty, ALGORITHMS
  • Orta Doğu Teknik Üniversitesi Adresli: Hayır

Özet

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.