Computer Science – Computational Geometry
Scientific paper
2004-07-08
Computer Science
Computational Geometry
Submitted to SODA05
Scientific paper
We study the problem of covering a given set of $n$ points in a high, $d$-dimensional space by the minimum enclosing polytope of a given arbitrary shape. We present algorithms that work for a large family of shapes, provided either only translations and no rotations are allowed, or only rotation about a fixed point is allowed; that is, one is allowed to only scale and translate a given shape, or scale and rotate the shape around a fixed point. Our algorithms start with a polytope guessed to be of optimal size and iteratively moves it based on a greedy principle: simply move the current polytope directly towards any outside point till it touches the surface. For computing the minimum enclosing ball, this gives a simple greedy algorithm with running time $O(nd/\eps)$ producing a ball of radius $1+\eps$ times the optimal. This simple principle generalizes to arbitrary convex shape when only translations are allowed, requiring at most $O(1/\eps^2)$ iterations. Our algorithm implies that {\em core-sets} of size $O(1/\eps^2)$ exist not only for minimum enclosing ball but also for any convex shape with a fixed orientation. A {\em Core-Set} is a small subset of $poly(1/\eps)$ points whose minimum enclosing polytope is almost as large as that of the original points. Although we are unable to combine our techniques for translations and rotations for general shapes, for the min-cylinder problem, we give an algorithm similar to the one in \cite{HV03}, but with an improved running time of $2^{O(\frac{1}{\eps^2}\log \frac{1}{\eps})} nd$.
No associations
LandOfFree
Minimum Enclosing Polytope in High Dimensions 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 Minimum Enclosing Polytope in High Dimensions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Enclosing Polytope in High Dimensions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-222163