Convex Hulls Under Uncertainty

摘要: We study the convex-hull problem in a probabilistic setting, motivated by need to handle data uncertainty inherent many applications, including sensor databases, location-based services and computer vision. In our framework, of each input point is described probability distribution over finite number possible locations null location account for non-existence point. Our results include both exact approximation algorithms computing query lying inside convex hull input, time-space tradeoffs membership queries, connection between Tukey depth as well new notion β-hull that may be useful representation uncertain hulls.