smaller core-sets for balls
Given a set of points P ? R d 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.
point value approximation paper size algorithm cluster timing computation fit core