# Approximate Convex Hull of Data Streams

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Dec 2017.

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

- [To what extent should we trust AI models when they extrapolate?](https://mlsanity.com/paper/2201.11260/) (2022)
- [How Reusable Are Benchmarks with Richer Feedback?](https://mlsanity.com/paper/2609.32109/) (2026)

## Abstract (arXiv)

Given a finite set of points P subseteq ℝd, we would like to find a small subset S subseteq P such that the convex hull of S approximately contains P. More formally, every point in P is within distance ε from the convex hull of S. Such a subset S is called an ε-hull. Computing an ε-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many real world applications, the set P is too large to fit in memory. We consider the streaming model where the algorithm receives the points of P sequentially and strives to use a minimal amount of memory. Existing streaming algorithms for computing an ε-hull require O(ε-(d-1)/2) space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an ε-hull of P, which we denote by OPT, can be much smaller. A natural question is whether a streaming algorithm can compute an ε-hull using only O(OPT) space. We begin with lower bounds that show that it is not possible to have a single-pass streaming algorithm that computes an ε-hull with O(OPT) space. We instead propose three relaxations of the problem for which we can compute ε-hulls using space near-linear to the optimal size. Our first algorithm for points in ℝ2 that arrive in random-order uses O(log n· OPT) space. Our second algorithm for points in ℝ2 makes O(log(frac1ε)) passes before outputting the ε-hull and requires O(OPT) space. Our third algorithm for points in ℝd for any fixed dimension d outputs an ε-hull for all but δ-fraction of directions and requires O(OPT · log OPT) space.