一尘不染

点间最短距离算法

algorithm

给定平面上的一组点,找到由这些点中的任意两个点形成的最短线段。

我怎样才能做到这一点?简单的方法显然是计算每个距离,但是我需要另一种算法进行比较。


阅读 264

收藏
2020-07-28

共1个答案

一尘不染

http://en.wikipedia.org/wiki/Closest_pair_of_points

可以使用递归分治法在O(n log n)时间内解决问题,例如:

  • 沿x坐标对点进行排序
  • 用垂直线x = xmid将点集分成两个相等大小的子集
  • 左右子集中递归解决问题。这将分别给出左侧和右侧的最小距离dLmin和dRmin。
  • 在一对点之间找到最小距离dLRmin,其中一个点位于垂直分割线的左侧,第二个点位于右侧。
  • 最终答案是dLmin,dRmin和dLRmin中的最小值。
2020-07-28