两个二维凸多边形之间最接近的特征点对

Question

问题是找到两个2D凹多边形之间最接近的特征。这些特征可以是顶点、边缘。因此结果可以是任意组合的特征。有没有比O(m*n)更好的复杂度的简单解决方案？其中m，n分别是多边形的边数。这些多边形是共面的。

- innochenti

---

修正的复杂度公式。 - innochenti

“n”是什么？难道多边形的数量不总是2吗？ - Alex Churchill

哦，我明白了。m是第一个的边缘/顶点数，n是第二个的数量。 - Alex Churchill

嗯...如果你只关心顶点，你可以用O(n log m + m log n)的时间复杂度完成--参见http://www.sciencedirect.com/science/article/pii/0167865583900417。你总是可以找到两个最近顶点对，然后只处理多边形中它们之间的边，但由于它们是凹多边形，这个数量仍然可能是O(m)，但对于大多数情况，你将会是O(m log n + n log m)。 - Alex Churchill

@alex c 很抱歉，我无法访问sciencedirect。 - innochenti

Answer 1

似乎存在一个时间复杂度为O(n.log(m))的算法，请参考这篇论文和这个问题。

我提出的一个优化方案：(未经测试)

如果你的多边形大部分时间都相距足够远，你可以构建两个凸包，并回到最简单的问题，即找到两个凸多边形之间的Hausdorff距离（解决方案为O(n+m)）。如果距离为0，则必须回到O(m.log(n))的情况，但如果大部分时间处于“凸包”情况且距离为正值，则这是值得的。

后记。我刚意识到，为了让假设成立，你还需要检查凸包中最近的特征是否属于原始凹多边形。如果不是，很容易找到反例（想象一个形状像字母C的多边形，旁边还有一个圆形：CO）。

因此更新后的推论是：两个凹多边形之间的豪斯多夫距离d是它们凸包之间的豪斯多夫距离，如果d > 0，且两个最近特征都是原始多边形的一部分。

留给读者作为练习的是证明这一点。

- Laurent Grégoire

---

不幸的是，在病态情况下，我相当确定这个假设意味着这种方法永远不会比O(mn)更好。想象一下以下设置：我们有{(0, 0.1)}和{(-1, 0)，(a, -0.5)，(1, 0)}，其中a = -n到n，a不等于0。然后(-1, 0)和(1,0)是通过凸逼近最接近的点，但真正最接近的点在凸包的对面（实际上是距离两个最近顶点最远的边缘）。话虽如此，凸包方法几乎总是一个很好的近似。 - Alex Churchill

是的，这就是我评论的重点：“属于原始凹多边形”。如果你有了这个，你所提出的情况就被覆盖了，回到了O(m.log(n))的情况（而不是O(nm)）。如果你总是处于“病态”情况下，我的优化显然不会带来任何好处，但是经验表明，在真实数据中，你必须支持少于百分之几的病态情况 - 但仍然必须支持它。 - Laurent Grégoire

你对于任意（可能是凹形）顶点的问题做出的分析完全正确，但请记住O(m log(n)) -- 更确切地说是 O(m log(n) + n log(m)) -- 情况并不涉及边缘，而是离散集合（等同于顶点）。我的病态案例旨在找到最近的特征边缘，而我不知道非离散凹集合的 O(m log(n)) 算法。 - Alex Churchill