A Space-Optimal Data-Stream Algorithm for Coresets in the Plane

Written with Pankaj Agarwal.

In Proc. 23rd Annual Symposium on Computational Geometry, pages 1-10, 2007.

Downloads: PDF, PS

Abstract: Given a point set P in R², a subset Q is an ε-kernel of P if for every slab W containing Q, the (1+ε)-expansion of W also contains P. We present a data-stream algorithm for maintaining an ε-kernel of a stream of points in R² that uses O(1/ε^1/2) space and takes O(log (1/ε)) amortized time to process each point. This is the first space-optimal data-stream algorithm for this problem.