Optimal core-sets for balls

Given a set of points P⊂Rd and value ε>0, an ε-core-set S⊂P has the property that the smallest ball containing S has radius within 1+ε of the radius of the smallest ball containing P. This paper shows that any point set has an ε-core-set of size ⌈1/ε⌉, and this bound is tight in the worst case. Some experimental results are also given, comparing this algorithm with a previous one, and with a more powerful, but slower one.