Maintaining the Approximate Extent Measures of
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.