# Convex Hulls under Uncertainty

arXiv: https://arxiv.org/abs/1406.6599 · HTML: https://mlsanity.com/paper/1406.6599/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 25 Jun 2014.

## Built on by (most cited first, 1 of 1)

- [Improving Medical Diagnostics with Vision-Language Models: Convex Hull-Based Uncertainty Analysis](https://mlsanity.com/paper/2412.00056/) (2024)

## Abstract (arXiv)

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 site 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 some-hull that may be a useful representation of uncertain hulls.