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

Question

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

Answer 1

This paper阐述了找出两个通用凸集之间距离的问题。

他们继续并提供大量的应用程序，包括两个凸多面体之间的距离。两个多面体之间的最小距离是寻找最大分离超平面的对偶。他们提供这个问题的表述，并显示为一个实现Gordan's Theorem of Alternatives的证明。公式（11.1）提供了你所要求的公式，但需要一些操作来将多面体带到这种形式。根据选定的标准，问题可以重新排列为线性（L1标准），二次（L2标准）或通用程序。

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

摘要：

在本文中，我们探索表征至少 规范问题，对偶关系。本文首先介绍了一个新的最小规范 对偶（MND）定理，它考虑了两个凸集之间的距离。粗略地说，新定理说，两组之间的最短距离等于组之间的最大“分离” ，其中术语“分离”是指分离两组的平行超平面之间的距离 。

本文的第二部分介绍了几个应用实例。 这些例子教授关于双重性在至少 规范问题中的作用的宝贵经验，并揭示这些问题的新特征。一课 揭示极性分解，其表征线性不等式的不一致系统的“解决方案”的特征。另一个教训揭示了MND定理，替代定理，最速下降方向和建构性最优性条件之间的密切联系。

我希望这有助于！