Math @ Duke

Publications [#235493] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Yu, H, A spaceoptimal datastream algorithm for coresets in the plane,
Proceedings of the Annual Symposium on Computational Geometry
(2007),
pp. 110 [doi]
(last updated on 2018/07/19)
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 datastream 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 spaceoptimal datastream 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 277080320

