An almost space-optimal streaming algorithm for coresets in fixed dimensions

We present a new streaming algorithm for maintaining an ε-kernel of a point set in Rd using O((1/ε(d−1)/2) log(1/ε)) space. The space used by our algorithm is optimal up to a small logarithmic factor. This significantly improves (for any fixed dimension d> 3) the best previous algorithm for this problem that uses O(1/εd−(3/2)) space, presented by Agarwal and Yu. Our algorithm immediately improves the space complexity of the previous streaming algorithms for a number of fundamental geometric optimization problems in fixed dimensions, including width, minimum-volume bounding box, minimum-radius enclosing cylinder, minimum-width enclosing annulus, etc.