给定平面上的一组点，找到由这些点中的任意两个点形成的最短线段。
我怎样才能做到这一点？最简单的方法显然是计算每个距离，但我需要另一种算法来比较。
http://en.wikipedia.org/wiki/Closest_pair_of_points http://en.wikipedia.org/wiki/Closest_pair_of_points
使用递归分而治之方法可以在 O(n log n) 时间内解决该问题，例如，如下所示：
- 沿 x 坐标对点进行排序
- 通过垂直线 x = xmid 将点集分成两个大小相等的子集
- 在左右子集中递归地解决问题。这将分别给出左侧和右侧最小距离 dLmin 和 dRmin。
- 求一对点之间的最小距离 dLRmin，其中一个点位于垂直分割线的左侧，第二个点位于垂直线的右侧。
- 最终的答案是 dLmin、dRmin 和 dLRmin 中的最小值。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
