Convex Hulls Under Uncertainty

Convex Hulls Under Uncertainty

0.00 Avg rating0 Votes
Article ID: iaor20173252
Volume: 79
Issue: 2
Start Page Number: 340
End Page Number: 367
Publication Date: Oct 2017
Journal: Algorithmica
Authors: , , , ,
Keywords: datamining, probability, programming: probabilistic, optimization
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 β equ1 ‐hull that may be a useful representation of uncertain hulls.

Reviews

Required fields are marked *. Your email address will not be published.