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

Math @ Duke





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

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


Publications [#235346] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharathkumar, R, Streaming Algorithms for Extent Problems in High Dimensions, Algorithmica, vol. 72 no. 1 (2015), pp. 83-98, ISSN 0178-4617 [doi]
    (last updated on 2017/12/17)

    Abstract:
    © 2013, Springer Science+Business Media New York.We present (single-pass) 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 sub-linear in n. For the problems of computing diameter, width and minimum enclosing ball of S, we obtain lower bounds on the worst-case 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 farthest-point 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 27708-0320