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 / √ ɛ) algorithm for producing an enclosing ball whose radius is at most ɛ away from the optimum. In the case of MECP our algorithm takes O(1/ɛ) iterations to converge. In both cases we improve the existing results due to Core-Sets which yield a O(nd/ɛ) greedy algorithm for the MEB and Panigrahy’s algorithm for MECP which takes O(1/ɛ 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. 1