Maintaining the Approximate Extent Measures of Moving Points

S. Har-Peled and P.K. Agarwal

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² so that the number of events is only a constant. This contrasts with Omega(n²) events that data structures for the maintenance of those exact properties have to handle.

Postscript : PDF.

Presentation

Animations

@string{SODA12  = "Proc. 12th ACM-SIAM Sympos. Discrete Algorithms"}

@InProceedings{ah-maemm-01,
  author = {P.K.~Agarwal and S.~Har-Peled},
  title = {Maintaining the Approximate Extent Measures of Moving Points},
  booktitle = SODA12,
  year = 2001, 
  pages = {148--157}
}

Last modified: Wed Jul 20 16:02:06 CDT 2011