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 language | English (US) |
---|---|
Pages (from-to) | 340-367 |
Number of pages | 28 |
Journal | Algorithmica |
Volume | 79 |
Issue number | 2 |
DOIs | |
State | Published - Oct 1 2017 |
Keywords
- Convex hull
- Membership probability
- Tukey depth
- Uncertainty
ASJC Scopus subject areas
- General Computer Science
- Computer Science Applications
- Applied Mathematics