论文标题
用于在多层室中查找最近点的方法的加速技术，并计算两个多面体之间的距离
An acceleration technique for methods for finding the nearest point in a polytope and computing the distance between two polytopes
论文作者
论文摘要
我们为一种任意方法提供了一种简单有效的加速技术，用于计算点上的欧几里得投影在凸多角体上，该点定义为有限点的凸壳，如果多型点中的点数比空间的维度大得多。该技术包括将任何给定方法应用于原始多层的“小”亚物种并逐渐移动，直到将给定点的投影投影到亚电视上，其投影与原始多层的投影相吻合。数值实验的结果证明了提出的加速技术的高效率。特别是，他们表明，计算时间的减少随多物体中的点数的增加而增加，并且对于某些方法，与此数字成正比。在本文的第二部分中，我们还讨论了提出的加速技术的直接扩展，以计算两种凸多属的距离的任意方法，定义为有限点的凸壳。
We present a simple and efficient acceleration technique for an arbitrary method for computing the Euclidean projection of a point onto a convex polytope, defined as the convex hull of a finite number of points, in the case when the number of points in the polytope is much greater than the dimension of the space. The technique consists in applying any given method to a "small" subpolytope of the original polytope and gradually shifting it, till the projection of the given point onto the subpolytope coincides with its projection onto the original polytope. The results of numerical experiments demonstrate the high efficiency of the proposed acceleration technique. In particular, they show that the reduction of computation time increases with an increase of the number of points in the polytope and is proportional to this number for some methods. In the second part of the paper, we also discuss a straightforward extension of the proposed acceleration technique to the case of arbitrary methods for computing the distance between two convex polytopes, defined as the convex hulls of finite sets of points.
