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

Math @ Duke



Publications [#235436] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Hal-Peled, S, Maintaining approximate extent measures of moving points, in Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (2001), pp. 148-157
    (last updated on 2018/10/16)

    We present approximation algorithms for maintaining various descriptors of the extent of moving points in R d. We first describe a data structure for maintaining the smallest orthogonal rectangle containing the point set. We then use this data structure to maintain the approximate diameter, smallest enclosing disk, width, and smallest area or perimeter bounding rectangle of a set of moving points in R 2 so that the number of events is only a constant. This contrasts with &OHgr;(n 2) events that data structures for the maintenance of those exact properties have to handle. Copyright © 2009 ACM, Inc.
ph: 919.660.2800
fax: 919.660.2821

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