Convex Hulls Under Uncertainty

Pankaj K. Agarwal, Sariel Har-Peled, Subhash Suri, Hakan Yıldız, Wuzhou Zhang

Research output: Contribution to journalArticle

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 languageEnglish (US)
Pages (from-to)340-367
Number of pages28
JournalAlgorithmica
Volume79
Issue number2
DOIs
StatePublished - Oct 1 2017

Fingerprint

Convex Hull
Query
Uncertainty
Location based services
Approximation algorithms
Probability distributions
Computer vision
Exact Algorithms
Computer Vision
Nonexistence
Null
Approximation Algorithms
Sensors
Probability Distribution
Trade-offs
Sensor
Computing
Framework

Keywords

  • Convex hull
  • Membership probability
  • Tukey depth
  • Uncertainty

ASJC Scopus subject areas

  • Computer Science(all)
  • Computer Science Applications
  • Applied Mathematics

Cite this

Agarwal, P. K., Har-Peled, S., Suri, S., Yıldız, H., & Zhang, W. (2017). Convex Hulls Under Uncertainty. Algorithmica, 79(2), 340-367. https://doi.org/10.1007/s00453-016-0195-y

Convex Hulls Under Uncertainty. / Agarwal, Pankaj K.; Har-Peled, Sariel; Suri, Subhash; Yıldız, Hakan; Zhang, Wuzhou.

In: Algorithmica, Vol. 79, No. 2, 01.10.2017, p. 340-367.

Research output: Contribution to journalArticle

Agarwal, PK, Har-Peled, S, Suri, S, Yıldız, H & Zhang, W 2017, 'Convex Hulls Under Uncertainty', Algorithmica, vol. 79, no. 2, pp. 340-367. https://doi.org/10.1007/s00453-016-0195-y
Agarwal PK, Har-Peled S, Suri S, Yıldız H, Zhang W. Convex Hulls Under Uncertainty. Algorithmica. 2017 Oct 1;79(2):340-367. https://doi.org/10.1007/s00453-016-0195-y
Agarwal, Pankaj K. ; Har-Peled, Sariel ; Suri, Subhash ; Yıldız, Hakan ; Zhang, Wuzhou. / Convex Hulls Under Uncertainty. In: Algorithmica. 2017 ; Vol. 79, No. 2. pp. 340-367.
@article{36de7ba92389418bbb94426196c646a1,
title = "Convex Hulls Under Uncertainty",
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.",
keywords = "Convex hull, Membership probability, Tukey depth, Uncertainty",
author = "Agarwal, {Pankaj K.} and Sariel Har-Peled and Subhash Suri and Hakan Yıldız and Wuzhou Zhang",
year = "2017",
month = "10",
day = "1",
doi = "10.1007/s00453-016-0195-y",
language = "English (US)",
volume = "79",
pages = "340--367",
journal = "Algorithmica (New York)",
issn = "0178-4617",
publisher = "Springer New York",
number = "2",

}

TY - JOUR

T1 - Convex Hulls Under Uncertainty

AU - Agarwal, Pankaj K.

AU - Har-Peled, Sariel

AU - Suri, Subhash

AU - Yıldız, Hakan

AU - Zhang, Wuzhou

PY - 2017/10/1

Y1 - 2017/10/1

N2 - 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.

AB - 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.

KW - Convex hull

KW - Membership probability

KW - Tukey depth

KW - Uncertainty

UR - http://www.scopus.com/inward/record.url?scp=84982102951&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84982102951&partnerID=8YFLogxK

U2 - 10.1007/s00453-016-0195-y

DO - 10.1007/s00453-016-0195-y

M3 - Article

AN - SCOPUS:84982102951

VL - 79

SP - 340

EP - 367

JO - Algorithmica (New York)

JF - Algorithmica (New York)

SN - 0178-4617

IS - 2

ER -