Math @ Duke

Publications [#235346] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharathkumar, R, Streaming Algorithms for Extent Problems in High Dimensions,
Algorithmica, vol. 72 no. 1
(2015),
pp. 8398, ISSN 01784617 [doi]
(last updated on 2018/10/16)
Abstract: © 2013, Springer Science+Business Media New York.We present (singlepass) streaming algorithms for maintaining extent measures of a stream S of n points in $\mathbb{R} ^{d}$. We focus on designing streaming algorithms whose working space is polynomial in d (poly(d)) and sublinear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worstcase approximation ratio of any streaming algorithm that uses poly(d) space. On the positive side, we introduce the notion of blurred ball cover and use it for answering approximate farthestpoint queries and maintaining approximate minimum enclosing ball and diameter of S. We describe a streaming algorithm for maintaining a blurred ball cover whose working space is linear in d and independent of n.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

