Math @ Duke

Publications [#235353] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HarPeled, S; Suri, S; YIldIz, H; Zhang, W, Convex hulls under uncertainty,
Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8737 LNCS
(January, 2014),
pp. 3748, ISSN 03029743, ISBN 9783662447765 [doi]
(last updated on 2018/12/16)
Abstract: We study the convexhull problem in a probabilistic setting, motivated by the need to handle data uncertainty inherent in many applications, including sensor databases, locationbased 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 nonexistence 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, timespace 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. © 2014 SpringerVerlag Berlin Heidelberg.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

