computational-geometry - 两个多边形/多面体的最佳近似对

Question

R^3 中有两个多面体 A 和 B，有空交集。多面体由它的面定义，即它的超空间只有不等式，顶点是未知的。问题是找到 A 中的点 a 和 B 中的 b 使得 ||ab|| = d(A,B) -- A 和 B 之间的距离。我们也可以为 R^2 或 R^d 为 d>3 制定此问题。解决这个问题的方法是什么。这个问题有一些应用吗？

Answer 1

本文阐述了寻找两个通用凸集之间距离的问题。

它们继续提供大量应用，包括两个凸多面体之间的距离。两个多面体之间的最小距离是找到最大分离超平面的对偶。他们提供了这个问题的公式，并作为一个实现展示了Gordan's Theorem of Alternatives 的证明。公式 (11.1) 提供了您所要求的公式，但需要进行一些操作才能将多面体带入该形式。根据选择的范数，可以将问题重铸为线性（L1范数）、二次（L2范数）或一般规划。

此外，其中给出的参考文献（关于在多面体中找到最近的点）是相关的。

抽象的：

在本文中，我们探讨了表征最小范数问题的对偶关系。本文首先提出了一个新的最小范数对偶 (MND) 定理，该定理考虑了两个凸集之间的距离。粗略地说，新定理说两个集合之间的最短距离等于集合之间的最大“分离”，其中“分离”一词是指将两个集合分开的一对平行超平面之间的距离。

论文的第二部分带来了几个应用示例。这些例子教导了关于对偶在最小范数问题中的作用的宝贵经验，并揭示了这些问题的新特征。一课揭示了极分解，它表征了一个不一致的线性不等式系统的“解”。另一课揭示了 MND 定理、备选定理、最陡下降方向和建设性最优条件之间的密切联系。

我希望这有帮助！