分治法求解最近点对问题（python实现）

问题描述

在一个点集合中找到一对距离最近的点。（二维点）

解决办法

1. 枚举

比较
p0, p1; p0, p2; p0, p3...
p1, p2; p1, p3...
...

def find_c_p(arr):
    size = len(arr)
    mid_d = distance(arr[0], arr[1])
    x, y = 0, 0
    for i in range(size):
        for j in range(i+1, size):
            if i!=j:
                d = distance(arr[i], arr[j])
                if d<mid_d:
                    mid_d = d
                    x, y = arr[i], arr[j]
    return mid_d, x, y

1. 分治法

枚举的时间复杂度是n的平方，用分治法可降低时间复杂度。

准备： 对于点集S，首先将S中的点按照x坐标排序，排序结果保存到A中，同时，将S点按y坐标排序，结果保存到B
思路： 集合A中的点划分左右两个子集，递归地找到子集中的解，取较小者，存为d，再考虑横跨左右区间的点对，取B中x坐标值在[mid-d, mid+d]中的点，保存到集合R中，此时，R内点按y坐标有序排布，找到R中的解，与d比较，返回最小者
代码

def find_closet_points(ls: list):
    a_a = sorted(ls, key=lambda x:x[0])
    a_b = sorted(ls, key=lambda x:x[1])

    def fun(a, b, left, right):
        if right - left <= 4:
            return find_c_p(a[left: right+1])
        if left < right:
            mid = (left + right) // 2
            d_l, plx, ply = fun(a, b, left, mid-1)
            d_r, prx, pry = fun(a, b, mid+1, right)
            if d_l < d_r:
                d = d_l
                ansx, ansy = plx, ply
            else:
                d = d_r
                ansx, ansy = prx, pry
            point = a[mid]
            b1 = find_points(d, point[0], b)
            d_b, px, py = find_closet(b1)
            if d_b<d:
                return d_b, px, py
            return d, ansx, ansy
    def find_points(radius, center, b):
        l, r = center-radius, center+radius
        b1 = []
        for x, y in b:
            if l <= x <= r:
                b1.append([x, y])
        return b1

    def find_closet(b1):
        size = len(b1)
        min_d = distance(b1[1], b1[0])
        x, y = 0, 0
        for i in range(size):
            for j in range(size-i):
                if j == 8:
                    break
                if i != j:
                    dis = distance(b1[i], b1[j])
                    if dis < min_d:
                        min_d = dis
                        x, y = b1[i], b1[j]
        return min_d, x, y

    return fun(a_a, a_b, 0, len(a_a) - 1)
def distance(p1, p2):
    return (p1[0] - p2[0]) ** 2 + (p1[1] - p2[1]) ** 2

参考资料李春葆《算法设计与分析》