2026-07-25T05:49:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:9025 2024-03-06T10:43:11Z ddc:004 open_access

Approximate Convex Hull of Data Streams Blum, Avrim Braverman, Vladimir Kumar, Ananya Lang, Harry Yang, Lin F. Convex Hulls Streaming Algorithms Epsilon Kernels Sparse Coding Given a finite set of points P subseteq R^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 epsilon from the convex hull of S. Such a subset S is called an epsilon-hull. Computing an epsilon-hull is an important problem in computational geometry, machine learning, and approximation algorithms. In many 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 epsilon-hull require O(epsilon^{(1-d)/2}) space, which is optimal for a worst-case input. However, this ignores the structure of the data. The minimal size of an epsilon-hull of P, which we denote by OPT, can be much smaller. A natural question is whether a streaming algorithm can compute an epsilon-hull using only O(OPT) space. We begin with lower bounds that show, under a reasonable streaming model, that it is not possible to have a single-pass streaming algorithm that computes an epsilon-hull with O(OPT) space. We instead propose three relaxations of the problem for which we can compute epsilon-hulls using space near-linear to the optimal size. Our first algorithm for points in R^2 that arrive in random-order uses O(log n * OPT) space. Our second algorithm for points in R^2 makes O(log(epsilon^{-1})) passes before outputting the epsilon-hull and requires O(OPT) space. Our third algorithm, for points in R^d for any fixed dimension d, outputs, with high probability, an epsilon-hull for all but delta-fraction of directions and requires O(OPT * log OPT) space. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Avrim Blum and Vladimir Braverman and Ananya Kumar and Harry Lang and Lin F. Yang 2018 Is Part Of LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2018.21 urn:nbn:de:0030-drops-90254 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.21 eng https://creativecommons.org/licenses/by/3.0/legalcode