Computing the Signed Distance Between Overlapping Ellipsoids
Computing the Signed Distance Between Overlapping Ellipsoids
复制标题
DOI：
10.1137/140979654
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
S. Iwata;Y. Nakatsukasa;A. Takeda
中科院分区：
文献类型：
--
作者：
S. Iwata;Y. Nakatsukasa;A. Takeda
当两个椭圆形没有相交时，计算两个椭圆形之间的签名距离是一个凸优化问题，但是当椭圆形重叠时，它变成了非凸。因此，不能保证用于凸优化问题的有效算法在重叠的椭球之间找到正确的签名距离。在本文中，我们首先表明，计算签名距离等于沿Minkowski差异边界的规范最小化。然后，我们得出了一种具有运行时间$ O（n^6）$的算法，其中$ n $是椭圆形的尺寸，该算法在Minkowski差异的边界上获得了全局最小化器，因此提供了确切的签名距离。该算法首先找到满足Karush-kuhn--tucker（KKT）条件的所有点，然后确定具有最小签名距离的相关KKT点。计算KKT点的主要困难是它们是两个双变量有理方程的解决方案，它们的极是杆子不是kno的...
Computing the signed distance between two ellipsoids is a convex optimization problem when the two ellipsoids have no intersection, but it becomes nonconvex when the ellipsoids overlap. Efficient algorithms for convex optimization problems are thus not guaranteed to find the correct signed distance between overlapping ellipsoids. In this paper, we first show that computing the signed distance is equivalent to minimizing the norm along the boundary of the Minkowski difference. We then derive an algorithm with running time $O(n^6)$, where $n$ is the dimension of the ellipsoids, that obtains a global minimizer on the boundary of the Minkowski difference and hence provides the exact signed distance. The algorithm first finds all the points that satisfy the Karush--Kuhn--Tucker (KKT) conditions, and then identifies a relevant KKT point with the smallest signed distance. The primary difficulty in computing the KKT points is that they are the solutions of two bivariate rational equations, whose poles are not kno...