A space-optimal data-stream algorithm for coresets in the plane


Journal Article

Given a point set PR 2, a subset Q P 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 2 that uses O(1/ ) space and takes O(log (1/)) amortized time to process each point. This is the first space-optimal data-stream algorithm for this problem. Copyright 2007 ACM.

Full Text

Duke Authors

Cited Authors

  • Agarwal, PK; Yu, H

Published Date

  • October 22, 2007

Published In

  • Proceedings of the Annual Symposium on Computational Geometry

Start / End Page

  • 1 - 10

Digital Object Identifier (DOI)

  • 10.1145/1247069.1247071

Citation Source

  • Scopus