分治算法-最邻近点问题Finding the closest pair of points
问题描述：
输入：空间平面上点集Q 输出：距离最近的两个点对
问题简化：如果是在一个直线上找最近的点对，则可以使用排序，之后找最近最近点。
分治思路：
Divide 将其划分为两个部分Q1,Q2 T(n) = O(n)
Conquer 分别找最近点对<p1,p2>,<q1,q2> T(n) = 2T(n/2)
Merge 比较分开点附近的两个点距离<p3,q3>和找出的<p1,p2><q1,q2>的距离T(n)= O(n)
时间复杂度：T(n)=O(1) n=2
T(n)=2T(n/2)+O(n)=O(nlogn) n≥3
二维空间问题：
Divide阶段和Conquer阶段都和一维问题类似，使用x=m的直线划分为两个子部分，可以找出最近点对<p1,p2>,<q1,q2>，
令d=min{<p1,p2>,<q1,q2>}，则merge阶段的点一定在[m-d,m+d]范围内。
似乎是优化很多，但是最糟糕的的情况是在该范围内的点很多则对应起来还是会有n^2级复杂度。
更优化的方案：对一个点，在令一侧距离其小于d的点最多有6个。具体说明如下
如图，在L:x=m左侧区域中的点P(x0,y0)，则距离其小于d的点在以P的圆心，半径为d的圆内，
则在L:x=m右侧的部分圆一定在以(m,y0-d)为左下角顶点，(m+d,y0+d)为右上角顶点的矩形内，即图中红色矩形区域内。
在对该矩形进行分6块，长为2d/3,宽为d/2，则每个小矩形的内的点最长距离为5d/6(对角线)，即每个小矩形最多有一个点。
因为如果有两个点在同一个矩形则其最小距离不会是d。
因此对[m-d,m+d]范围内每个顶点最多有6个点需要判断。
需要注意的事项：
1. 要设定好数据结构便于处理
2. 要进行预处理，对点集分别按x，y排序，维护两个排序排序结合。
时间复杂度：T(n)=O(1) n=2
T(n)=O(n)+2T(n/2)+O(n)=O(nlogn) n≥3
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
