假设我们有两个多面体，是否有任何有效的方法可以只计算minkowski差的壳上的顶点？
我知道要得到一个单一的 shell 顶点，您会在A方向上找到一个多面体上最远的顶点，然后在-A方向上找到另一个多边形上最远的顶点。但是，对于每个顶点而言，至少要达到O(N ^ 2)。有没有更有效的方法？
最佳答案
有一种有效的方法可以计算凸多面体的Minkowski和(以及差异)。它描述于here。就两个多面体的边数而言，它是线性的。
由于对于任何点集，其Minkowski和的凸包都是其凸壳的Minkowski和，因此可以先计算凸包(使用Chan算法)，然后进行Minkowski和。