Computer Science – Computational Geometry
Scientific paper
2009-09-05
Computer Science
Computational Geometry
18 Pages Accepted in SODA 2011
Scientific paper
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/\sqrt{\epsilon})$ approximation algorithm for producing an enclosing ball whose radius is at most $\epsilon$ away from the optimum (where $\Qcal$ is an upper bound on the norm of the points). This improves existing results using \emph{coresets}, which yield a $O(nd/\epsilon)$ 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/\epsilon)$ 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 \citet{Nesterov05a} to obtain our results.
Saha Ankan
Vishwanathan S. V. N.
Zhang Xinhua
No associations
LandOfFree
New Approximation Algorithms for Minimum Enclosing Convex Shapes does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with New Approximation Algorithms for Minimum Enclosing Convex Shapes, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Approximation Algorithms for Minimum Enclosing Convex Shapes will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-723638