Publications [#235493] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Yu, H, A space-optimal data-stream algorithm for coresets in the plane, Proceedings of the Annual Symposium on Computational Geometry (October, 2007), pp. 1-10, ACM Press
    (last updated on 2023/06/02)

    Abstract:
    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.