2009/09/05 by Saha, Ankan, Vishwanathan, S. V. N., Zhang, Xinhua
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)
paper · doi:10.48550/arxiv.0909.1062
Given n points in a d dimensional Euclidean space, the Minimum Enclosing Ball (MEB) problem is to find the ball with the smallest radius which contains all n points. We give a O(nd\Qcal/√ε) approximation algorithm for producing an enclosing ball whose radius is at most ε away from the optimum (where \Qcal is an upper bound on the norm of the points). This improves existing results using coresets, which yield a O(nd/ε) greedy algorithm. Finding the Minimum Enclosing Convex Polytope (MECP) is a related problem wherein a convex polytope of a fixed shape is given and the aim is to find the smallest magnification of the polytope which encloses the given points. For this problem we present a O(mnd\Qcal/ε) approximation algorithm, where m is the number of faces of the polytope. Our algorithms borrow heavily from convex duality and recently developed techniques in non-smooth optimization, and are in contrast with existing methods which rely on geometric arguments. In particular, we specialize the excessive gap framework of \citetNesterov05a to obtain our results.