点间最短距离算法 [英] 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.

推荐答案

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

该问题可以使用递归分治法在 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屋！