Maintaining approximate extent measures of moving points
Published
Journal Article
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.
Duke Authors
Cited Authors
- Agarwal, PK; Hal-Peled, S
Published Date
- December 1, 2001
Published In
- Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms
Start / End Page
- 148 - 157
Citation Source
- Scopus