Adaptive sampling for geometric problems over data streams (Q2477195)

The paper presents an adaptive sampling scheme for summarizing a streaming set of two-dimensional points, using limited storage so that many natural geometric queries can be answered faithfully. This approach yields nice error bounds for a variety of approximation problems by convex sets. The convex hull of a set of points plays a major role in this work. In fact, a measure of quality is given in terms of the maximum distance from the true convex hull to the one of the sample set. The error analysis is based on uncertainty triangles, a notion introduced by the authors. The main result is Theorem 5.4. Given a stream of data points and an integer \(r\), it can be maintained an adaptive sample of at most \(2r+1\) points such that the distance from the true convex hull to the hull of the sample is \({\mathcal{O}}(D/r^2)\), where \(D\) is the current diameter of the sample set. The amortized time to update the sample after a new point is added is \({\mathcal{O}}(\log(r))\) in the worst case. The description of the adaptive convex hull algorithm and some experimental results are also given in the article.