Maintaining approximate extent measures of moving points
Pankaj K. Agarwal, Sariel Har-Peled · 2001
We present approximation algorithms for maintaining various descriptors of the extent of moving points in R . We rst 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, and smallest enclosing disk of a set of moving so that the number of events is only a constant. This contrasts with ) events that data structures for the maintenance of those exact properties have to handle.