Smaller core-sets for balls
Mihai Bâdoiu, Kenneth L. Clarkson · 2003
Given a set of points P ⊂ Rd and value ∊ > 0, an ∊-core-set S ⊂ P has the property that the smallest ball containing S is an ∊-approximation of the smallest ball containing P. This paper shows that any point-set has an ∊-core-set of size [2/∊]. We also give a fast algorithm that finds this core-set. 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/∊ + (l/∊)5) time to compute an ∊-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/∊2) time. This algorithm also implies slightly faster algorithms for computing approximately the smallest radius k-flat fitting a set of points.