点算法之间的最短距离 [英] Shortest distance between points algorithm
本文介绍了点算法之间的最短距离的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
鉴于在一个平面上的点的集合，发现由任意两个这些点形成的最短线段。的
我怎么能这样做？在平凡的方式显然是要计算每个距离，但我需要另一种算法来比较。
How can I do that? The trivial way is obviously to calculate each distance, but I need another algorithm to compare.
推荐答案
<一个href="http://en.wikipedia.org/wiki/Closest%5Fpair%5Fof%5Fpoints">http://en.wikipedia.org/wiki/Closest%5Fpair%5Fof%5Fpoints
这个问题可以在O解决使用递归的鸿沟（N log n）的时间，治之的办法，例如，如下：
The problem can be solved in O(n log n) time using the recursive divide and conquer approach, e.g., as follows:
- 排序点沿x坐标
- 由垂直线分割点的集合为两个大小相等的子集X = xmid
- 在左和右子集递归问题解决了。这会给左侧和右侧最小距离dLmin和dRmin分别
- 找到的一对点，其中一个点位于的分割垂直和第二点的左侧之间的最小距离dLRmin位于右侧。
- 最终的答案是最低之间dLmin，dRmin和dLRmin。
这篇关于点算法之间的最短距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
