Blum, Avrim ;
Braverman, Vladimir ;
Kumar, Ananya ;
Lang, Harry ;
Yang, Lin F.
Approximate Convex Hull of Data Streams
Abstract
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 epsilonhull. Computing an epsilonhull 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 epsilonhull require O(epsilon^{(1d)/2}) space, which is optimal for a worstcase input. However, this ignores the structure of the data. The minimal size of an epsilonhull of P, which we denote by OPT, can be much smaller. A natural question is whether a streaming algorithm can compute an epsilonhull 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 singlepass streaming algorithm that computes an epsilonhull with O(OPT) space. We instead propose three relaxations of the problem for which we can compute epsilonhulls using space nearlinear to the optimal size. Our first algorithm for points in R^2 that arrive in randomorder uses O(log n * OPT) space. Our second algorithm for points in R^2 makes O(log(epsilon^{1})) passes before outputting the epsilonhull and requires O(OPT) space. Our third algorithm, for points in R^d for any fixed dimension d, outputs, with high probability, an epsilonhull for all but deltafraction of directions and requires O(OPT * log OPT) space.
BibTeX  Entry
@InProceedings{blum_et_al:LIPIcs:2018:9025,
author = {Avrim Blum and Vladimir Braverman and Ananya Kumar and Harry Lang and Lin F. Yang},
title = {{Approximate Convex Hull of Data Streams}},
booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)},
pages = {21:121:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770767},
ISSN = {18688969},
year = {2018},
volume = {107},
editor = {Ioannis Chatzigiannakis and Christos Kaklamanis and D{\'a}niel Marx and Donald Sannella},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9025},
URN = {urn:nbn:de:0030drops90254},
doi = {10.4230/LIPIcs.ICALP.2018.21},
annote = {Keywords: Convex Hulls, Streaming Algorithms, Epsilon Kernels, Sparse Coding}
}
04.07.2018
Keywords: 

Convex Hulls, Streaming Algorithms, Epsilon Kernels, Sparse Coding 
Seminar: 

45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)

Issue date: 

2018 
Date of publication: 

04.07.2018 