也许您应该签出（ PDF警告！还要注意，由于某些原因，页面的顺序是颠倒的 ）Toussaint和Bhattacharya的“
计算两个有限平面集之间最小距离的最佳算法 ”：

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

如果两个多边形相交于凸多边形，也许您也应该签出（ PDF警告！同样，页面顺序颠倒了 ）Toussaint的“
计算两个相交凸多边形之间的最小顶点距离的最佳算法 ”：

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