We address the problem of Minimum Enclosing Ball (MEB) and its generalization
to Minimum Enclosing Convex Polytope (MECP). Given $n$ points in a $d$
dimensional Euclidean space, we give a $O(nd/\sqrt{\epsilon})$ algorithm for
producing an enclosing ball whose radius is at most $\epsilon$ away from the
optimum. In the case of MECP our algorithm takes $O(1/\epsilon)$ iterations to
converge. In both cases we improve the existing results due to \emph{Core-Sets}
which yield a $O(nd/\epsilon)$ greedy algorithm for the MEB and Panigrahy's
algorithm for MECP which takes $O(1/\epsilon^{2})$ iterations to converge by
including the most ``violating'' point into its active set at every iteration.
All our algorithms borrow heavily from recently developed techniques in
non-smooth optimization and convex duality and are in contrast with existing
methods which rely on the geometry of the problem. We raise a number of open
questions, provide partial answers, and discuss the difficulties in
generalizing our algorithms to arbitrary minimum enclosing norm balls.