Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


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 (2007), pp. 1-10 [doi]
    (last updated on 2017/12/18)

    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.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320