Efficient approximation algorithms for minimum enclosing convex shapes (2009)

Content Provider	CiteSeerX
Author	Vishwanathan, S. V. N. Saha, Ankan
Abstract	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
File Format	PDF
Publisher Date	2009-01-01
Access Restriction	Open
Subject Keyword	Non-smooth Optimization Minimum Enclosing Convex Polytope Minimum Enclosing Ball Greedy Algorithm Efficient Approximation Algorithm Active Set Norm Ball Violating Point Dimensional Euclidean Space Partial Answer Minimum Enclosing Convex Shape Convex Duality
Content Type	Text