Optimal Core-Sets for Balls

Given a set of points P Ì Rd and value e>0, an e-core-set SÌP has the property that the smallest ball containing S is within e of the smallest ball containing P. This paper shows that any point set has an e-core-set of size ceiling(1/e), and this bound is tight in the worst case. A faster algorithm given here finds an e-core-set of size at most 2/e. These results imply the existence of small core-sets for solving approximate k-center clustering and related problems. The sizes of these core-sets are considerably smaller than the previously known bounds, and imply faster algorithms; one such algorithm needs O(dn/e + (1/e)5) time to compute an e-approximate minimum enclosing ball (1-center) of n points in d dimensions. A simple gradient- descent algorithm is also given, for computing the minimum enclosing ball in O(dn/e2) time. This algorithm also implies slightly faster algorithms for computing approximately the smallest radius k-flat fitting a set of points.