Minimum Enclosing Polytope in High Dimensions
Minimum Enclosing Polytope in High Dimensions
复制标题
高维最小封闭多面体
DOI：
10.48550/arxiv.cs/0407020
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
R. Panigrahy
中科院分区：
文献类型：
--
作者：
R. Panigrahy
我们研究的问题，覆盖一组给定的$n$点在一个高，$d$维空间的最小封闭多面体的一个给定的任意形状。我们提出的算法，适用于一个大家庭的形状，提供要么只翻译，没有旋转是允许的，或只旋转一个固定点是允许的，也就是说，只允许缩放和平移一个给定的形状，或缩放和旋转的形状周围的一个固定点。我们的算法从一个被猜测为最佳大小的多面体开始，并根据贪婪原则迭代地移动它：简单地将当前多面体直接移动到任何外部点，直到它接触表面。为了计算最小封闭球，这给出了一个运行时间为O（nd/\eps）$的简单贪婪算法，产生一个半径为1 +\eps$乘以最优值的球。这个简单的原则推广到任意凸形状时，只允许平移，需要最多$O（1/\eps^2）$迭代。我们的算法意味着大小为O（1/\eps^2）$的{\em core-sets}不仅存在于最小封闭球，而且存在于任何具有固定方向的凸形。一个{\em Core-Set}是$poly（1/\eps）$ points的一个小子集，它的最小封闭多面体几乎和原始点一样大。虽然我们不能联合收割机我们的技术为一般形状的平移和旋转，对于最小圆柱体的问题，我们给出了一个算法类似于在\cite{HV 03}，但具有改进的运行时间为2 ^{O（\frac{1}{\eps^2}\log \frac{1}{\eps}）}和$。
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$.