计算两组点之间的最小距离的最快算法是什么？

我想找到两个多边形之间的最小距离。我必须找到第一个形状的每个顶点与另一个顶点的所有顶点之间的最短距离的最小值。类似于Hausdorff

Distance，但我需要最小值而不是最大值。

也许您应该签出（ PDF警告！还要注意，由于某些原因，页面的顺序是颠倒的 ）Toussaint和Bhattacharya的“

计算两个有限平面集之间最小距离的最佳算法 ”：

它被示出在本文中的两个平面的有限集之间的最小距离，如果[ 原文如此 ] n个点可以在O计算（ Ñ 登录 Ñ
）的最坏情况的运行时间，而这是最适合于一个常数因子内。此外，当集合形成凸多边形时，可以将复杂度降低为O（ n ）。

如果两个多边形相交于凸多边形，也许您也应该签出（ PDF警告！同样，页面顺序颠倒了 ）Toussaint的“

计算两个相交凸多边形之间的最小顶点距离的最佳算法 ”：

令 P = { p 1， p 2，…， pm }和Q = { q 1， q 2，…， qn
}是两个相交的多边形，其顶点由其直角坐标指定。最佳的O（米 + Ñ ）算法，用于计算顶点之间的最小欧氏距离p 我在 P 和一个顶点
q Ĵ在 Q 。