Home Bookmarks Papers Blog

Maintaining the Approximate Extent Measures of Moving Points

S. Har-Peled and P.K. Agarwal


Full (and improved) version.
We present approximation algorithms for maintaining various descriptors of the extent of moving points in Rd. 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 R2 so that the number of events is only a constant. This contrasts with Omega(n2) 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