Math @ Duke

Publications [#235436] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; HalPeled, S, Maintaining approximate extent measures of moving points,
in Twelfth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(2001),
pp. 148157
(last updated on 2018/03/17)
Abstract: 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.


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

