最近点对问题
【想法】最近点对的分治策略如下。
- 划分：将集合S分为S1和S2，根据平衡子问题的原则每个子集中大约有n/2个点，设集合S的最近点对是P(i)和P(j)（1 <= i, j <= n），则会出现以下三种情况。
-
1.1P(i)∈S1，P(j)∈S1，即最近点对均在S1中； -
1.2P(i)∈S2，P(j)∈S2，即最近点对均在S2中； -
1.3P(i)∈S1，P(j)∈S2，即最近点对分别在S1和S2中。
- 求解子问题：对于划分阶段的情况1.1和1.2可以递归求解，如果最近对在1.3的情况就比较复杂了。
- 合并：分别比较在划分阶段的三种情况下的点对，取三者之中的距离较小者为问题的解。
下面讨论划分阶段1.3的情况。为了将平面上的点集S分割为点的个数大致相同的两个子集S1和S2，选取垂直线x=m来作为分割线，其中，m为S中各点x坐标中位数。由此将S分割为S1={p∈S1 | x(p)<= m}和S2={q∈S2 | x(q)>m}。递归在S1和S2上，分别得到最近距离d1和d2，令d=min(d1,d2),如果最近对小于d则属于1.3的情况。不妨设p∈S1,q∈S2,则pq距离x=m距离均小于d，所以可以把求解限制在以x=m为中心宽度为2d的垂直带P1和P2中，垂直带外任何点对之间的距离都一定大于d。
假设点p(x,y)是集合P1和P2中y坐标最小的点，则点p可能zaiP1中也可能在P2中，现在需要找出和点p的距离小于d的点显然这样的点y坐标一定位于[y,y+d]之间，而且这样的点不会超过八个，因为P1和P2之间的点距离至少为d。所以可以将P1和P2中的点p(x,y)在y坐标区间按照y坐标升序排列，顺序处理P1和P2中的点p(x,y)，在y坐标区间[y,y+d]内取出最多8个候选点，计算它们和点p之间的距离。
【算法】简单起见。假设点集S已按x坐标升序排列，分治法求解最近对问题的算法伪代码描述如下。
输入：按x坐标升序排列的n(n>=2)个点的集合S={(x1,y1),(x2,y2)....(xn,yn)}
输出：最近点对的距离
- 如果n等于2，返回两个点煎的距离，算法结束；
- 划分：m=S中各点坐标x的中位数；
- d1=S1中最近对距离；
- d2=S2中最近对的距离；
- d=min(d1,d2);
- 一次考察集合S中的点，如果（x<=xm&&x>xm-d)则将该店放入P1中；如果（x>xm&&x<xm+d）,则将点放入P2中；
- 将集合P1和P2按y坐标升序排列；
- 对集合P1和P2中的每个点p(x,y),在y坐标区间[y,y+d]内最多取出8个候选点，计算与点p的最近距离d3；
- 返回min(d,d3);
github代码
注：感觉确实好长时间没有简书了，哦哦，最近忙着其它的事情，去了南京好几趟。其实文章早就写好了，但是代码没有完善，所以。。。。没办法我有强迫症，没代码不敢网上传啊，怕被拍砖。这个端午小长假，难得的休闲，估计会撸两天代码，多余的一天和小伙伴篮球走起。
网友评论