Maintaining approximate extent measures of moving points


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