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 two approximation algorithms for producing an enclosing ball whose radius is at most $\epsilon$ away from the optimum. The first requires $O(nd\mathcal{L}/sqrt{\epsilon})$ effort, where $\mathcal{L}$ is a constant that depends on the scaling of the data. The second is a $O^*(nd\mathcal{Q}/\sqrt{\epsilon})$ approximation algorithm, where $\mathcal{Q}$ is an upper bound on the norm of the points. For the Minimum Enclosing Convex Polytope (MECP) problem we give $O(mnd\mathcal{L}/\epsilon)$ and $O^*(mnd\mathcal{Q}/\epsilon)$ approximation algorithms, 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.

Joint work with SVN Vishwanathan and Xinhua Zhang.