Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235353] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Har-Peled, 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. 37-48, ISSN 0302-9743, ISBN 9783662447765 [doi]
    (last updated on 2023/06/02)

    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. © 2014 Springer-Verlag Berlin Heidelberg.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320