Approximating extent measures of points

We present a general technique for approximating various descriptors of the extent of a set P of n points in R-d when the dimension d is an arbitrary fixed constant. For a given extent measure mu and a parameter epsilon > 0, it computes in time O(n + 1/epsilon(O(1))) a subset Q subset of or equal to P of size 1/epsilon(O(1)), with the property that (1 - epsilon)mu(P) less than or equal to mu(Q) less than or equal to mu(P). The specific applications of our technique include epsilon-approximation algorithms for (i) computing diameter, width, and smallest bounding box, ball, and cylinder of P, (ii) maintaining all the previous measures for a set of moving points, and (iii) fitting spheres and cylinders through a point set P. Our algorithms are considerably simpler, and faster in many cases, than previously known algorithms.