求给定点集中最小欧氏距离点对。

可以先将点按照横坐标从小到大排序。然后使用分治法来求解最小距离。具体算法如下：

Step 1:

输入点集P，按照x坐标从小到大排序，得到点序列P[1...n]。

Step 2:

如果点集大小n<=3，直接用穷举法求解最小距离，返回结果。

Step 3:

将点集P分成左右两个子集Pl和Pr，每个子集大小不超过n/2。

• Pl包含P中x坐标小于等于x中间值的点；
• Pr包含P中x坐标大于x中间值的点。

Step 4:

递归地对Pl子集和Pr子集求解最小距离。

• 递归求解后得到左右两个子集的最小距离为d；
• 同时在排序的点序列P中，找到一个中间区域，其x坐标在[xmid-d,xmid+d]范围内；
• 在该中间区域内计算每个点与其后面最多7个点的距离，找到其中最小距离d’。

Step 5:

最终的最小距离为d和d'中的最小值。

代码示例：Python实现

import math

def distance(p1, p2): return math.sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

def brute_force(P): mini = float('inf') for i in range(len(P)): for j in range(i+1, len(P)): if distance(P[i], P[j]) < mini: mini = distance(P[i], P[j]) return mini

def strip_closest(strip, d): mini = d

for i