Improved 1+ε Approximation Algorithms for the Balls in High Dimensions via Core-Sets
Junfeng Luan · Computer Engineering and Science · 2010
The minimum enclosing ball problem means to construct a ball of the minimum radius enclosing a given set of balls in S. We propose the concept of the diameter of a set of balls and give an approximation algorithm solve the diameter. We develop the 1+e approximation algorithm using core-sets. The time complexity of this algorithm is O(nd/e+d2/e3/2(1/e+d)log(1/e)). We prove the existence of the core-sets of size O(1/e) are unrelated to n and d.