平面上最近点对

DestinHistoire · 2019-06-07 10:56:30 · 题解

【问题描述】

n个点在公共空间中，求出所有点对的欧几里得距离最小的点对

【分析】

  该题直观的解决方法是 Brute Force(暴力)。时间复杂度为O(n^2)

int minn=INF;
for(int i=1;i<=size(P)-1;i++)
{
    for(int j=i+1;j<=size(P);j++)
    {
        int a=P[i],b=P[j];
        minn=min(minn,distance(a,b));
        closest=(a,b);
    }
    return closest;
}

分治法求解

分解

  对所有的点按照 x 坐标(或者 y )从小到大排序(排序方法时间复杂度 O(nlogn))。根据下标进行分割，使得点集分为两个集合。

解决

  递归的寻找两个集合中的最近点对。取两个集合最近点对中的最小值 min(dis_{left},dis_{right})

合并

  最近距离不一定存在于两个集合中，可能一个点在集合 A ，一个点在集合 B，而这两点间距离小于 dis。
  其中如何合并是关键。根据递归的方法可以计算出划分的两个子集中所有点对的最小距离 disleft,disright，再比较两者取最小值，即 dis=min(dis_{left},dis_{right}) 。那么一个点在集合 A，一个在集合 B 中的情况，可以针对此情况，用之前分解的标准值，即按照 x 坐标(或者 y )从小到大排序后的中间点的 x 坐标作为 mid。划分一个 [mid-dis,mid+dis] 区域，如果存在最小距离点对，必定存在这个区域中。

  之后只需要根据左边区域 [mid-dis,mid] 的点来遍历右边区域 [mid,mid+dis] 的点，即可找到是否存在小于 dis 距离的点对。
  但是存在一个最坏情况，即通过左右两个区域计算得到的 dis 距离来划分的第三区域可能包含集合所有的点，这时候进行遍历查找，时间复杂度仍然和 brute force 方法相同，都为O(n^2)。因此需要对此进行深一步的考虑。

  1985年 Preparata 和 Shamos 在给出该问题的一个分治算法并且还具体分析了在 [mid-dis,mid+dis] 区域中出现的情况，若 (p,q) 是 Q 的最近点对，p 在带域左半部分，则 q 点必在下图所示的 \delta* 2\delta 长方形上，而在该长方形上，最多只能由右边点集的6个点。每个点对之间的距离不小于δ。

  此结论很好证明，通过在 \delta* 2\delta 上以 \frac{2\delta}{3}* \frac{\delta}{2} 划成 6 个小长方形

  用反证法来证明，假设存在大于6个点，则必有一个或多个小长方形存在两个及以上点，而小长方形的最长距离是为对角线长度，为：