最接近點對問題

1、三維空間最接近點問題三維空間最接近點問題v問題：給定平面上n個點，找其中的一對點，使得在n個點所組成的所有點對中，該點對間的距離最小。v說明：嚴(yán)格來講，最接近點對可能多于一對，為簡便起見，我們只找其中的一對作為問題的解。一個簡單的做法是將每一個點與其他n-1個點的距離算出，找出最小距離的點對即可。該方法的時間復(fù)雜性是T(n)=n(n-1)/2+n=O(n2)，效率較低。已經(jīng)證明，該算法的計算時間下界是(nlogn)。分治法解決二維空間最接近點問題分治法解決二維空間最接近點問題選取一垂直線選取一垂直線l:x=m來作為分割直線。其中來作為分割直線。其中m為為S中各中各點點x坐標(biāo)的中位數(shù)。由此將坐標(biāo)

2、的中位數(shù)。由此將S分割為分割為S1和和S2。遞歸地在遞歸地在S1和和S2上找出其最小距離上找出其最小距離d1和和d2，并設(shè)，并設(shè)d=mind1,d2，S中的最接近點對或者是中的最接近點對或者是d，或者是某個，或者是某個p,q，其中，其中pS1且且qS2。v第一步篩選：如果最近點對由第一步篩選：如果最近點對由S1中的中的p3和和S2中的中的q3組成，則組成，則p3和和q3一定在劃分線一定在劃分線L的距離的距離d內(nèi)。內(nèi)。v第二步篩選：考慮第二步篩選：考慮P1中任意一點中任意一點p，它若與，它若與P2中的點中的點q構(gòu)成最接近點對的候選者，則必構(gòu)成最接近點對的候選者，則必有有distance(p，q)

3、d。滿足這個條件的。滿足這個條件的P2中的點一定落在一個中的點一定落在一個d2d的矩形的矩形R中中R中的點具有稀疏性中的點具有稀疏性uP2中任何中任何2個個S中的點的距離都不小于中的點的距離都不小于d。由。由此可以推出矩形此可以推出矩形R中最多只有中最多只有6個個S中的點。中的點。u在分治法的合并步驟中最多只需要檢查在分治法的合并步驟中最多只需要檢查6n/2=3n個候選點對！個候選點對！R中最多只有6個S中的點證明證明:將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導(dǎo)出6個(d/2)(2d/3)的矩形。 若矩形R中有多于6個S中的點，則由鴿舍原理易知至少有一個(d/2)(2d/3)

4、的小矩形中有2個以上S中的點。 設(shè)u，v是位于同一小矩形中的2個點，則222223625) 3/2()2/()()()()(dddvyuyvxuxdistance(u,v)d。這與d的意義相矛盾。* 鴿舍原理（也稱抽屜原理）鴿舍原理（也稱抽屜原理）把把n+1個球，放入個球，放入n個抽屜，則一定有一個抽屜內(nèi)至少有個抽屜，則一定有一個抽屜內(nèi)至少有2個球。個球。P2中與點中與點p最接近這最接近這6個候選點的縱坐標(biāo)與個候選點的縱坐標(biāo)與p的縱坐標(biāo)相差不超過的縱坐標(biāo)相差不超過d.因此，若將因此，若將P1和和P2中所有中所有S中點中點按其按其y坐標(biāo)坐標(biāo)排好序排好序，則對，則對P1中所有點，對排好序的點列中所

5、有點，對排好序的點列作一次掃描，就可以找出所有最接近點對的候作一次掃描，就可以找出所有最接近點對的候選者。對選者。對P1中每一點最多只要檢查中每一點最多只要檢查P2中排好中排好序的相繼序的相繼6個點。個點。如何確定要檢查哪6個點double cpair2(S) n=|S|; if (n 2) return ;1、m=S中各點中各點x間坐標(biāo)的中位數(shù)間坐標(biāo)的中位數(shù); 構(gòu)造構(gòu)造S1和和S2； /S1=pS|x(p)m2、d1=cpair2(S1); d2=cpair2(S2); 3、dm=min(d1,d2);4、設(shè)、設(shè)P1是是S1中距垂直分割線中距垂直分割線l的距離在的距離在dm之之內(nèi)的所有點組成

6、的集合；內(nèi)的所有點組成的集合； P2是是S2中距分割線中距分割線l的距離在的距離在dm之內(nèi)所有之內(nèi)所有點組成的集合；點組成的集合； 將將P1和和P2中點依其中點依其y坐標(biāo)值排序；坐標(biāo)值排序； 并設(shè)并設(shè)X和和Y是相應(yīng)的已排好序的點列；是相應(yīng)的已排好序的點列；5、通過掃描、通過掃描X以及對于以及對于X中每個點檢查中每個點檢查Y中與中與其距離在其距離在dm之內(nèi)的所有點之內(nèi)的所有點(最多最多6個個)可以完成可以完成合并；合并； 當(dāng)當(dāng)X中的掃描指針逐次向上移動時，中的掃描指針逐次向上移動時，Y中的中的掃描指針可在寬為掃描指針可在寬為2dm的區(qū)間內(nèi)移動；的區(qū)間內(nèi)移動； 設(shè)設(shè)dl是按這種掃描方式找到的點對間

7、的最是按這種掃描方式找到的點對間的最小距離；小距離；6、d=min(dm,dl); return d;O(n)2T(n/2)常數(shù)時間O(n)常數(shù)時間O(n)復(fù)雜度分析v、用了O(n)時間；v用了2T(n/2)時間v、用了常數(shù)時間v在預(yù)排序的情況下用時O(n) nnOnTnnnOnTOnTlog44)()2/(2) 1 ()(選取一垂平面選取一垂平面l:y=m來作為分割平面。其中來作為分割平面。其中m為為S中各中各點點y坐標(biāo)的中位數(shù)。由此將坐標(biāo)的中位數(shù)。由此將S分割為分割為S1和和S2。遞歸地在遞歸地在S1和和S2上找出其最小距離上找出其最小距離d1和和d2，并設(shè)，并設(shè)d=mind1,d2，S中

8、的最接近點對或者是中的最接近點對或者是d，或者是某個，或者是某個p,q，其中，其中pS1且且qS2。分治法解決三維空間最接近點問題分治法解決三維空間最接近點問題v第一步篩選：如果最近點對由第一步篩選：如果最近點對由S1中的中的p3和和S2中的中的q3組成，則組成，則p3和和q3一定在劃分平面一定在劃分平面L的距離的距離d內(nèi)。內(nèi)。v第二步篩選：考慮第二步篩選：考慮P1中任意一點中任意一點p，它若與，它若與P2中的點中的點q構(gòu)成最接近點對的候選者，則必構(gòu)成最接近點對的候選者，則必有有distance(p，q)d。滿足這個條件的。滿足這個條件的P2中的點定落在一個中的點定落在一個d2d2d的長方體的

9、長方體R中中u重要觀察結(jié)論：重要觀察結(jié)論：P2中任何中任何2個個S中的點的距離中的點的距離都不小于都不小于d。由此可以推出長方體。由此可以推出長方體R中最多只有中最多只有24個個S中的點。中的點。u在分治法的合并步驟中最多只需要檢在分治法的合并步驟中最多只需要檢24n/2=12n個候選點對。個候選點對。R中最多只有24個S中的點distance(u,v)d。這與d的意義相矛盾。由d的意義可知, P2 中任何2個S中的點的距離都不小于d. 由此可以推出長方體R中最多只有24個S 中的點. 事實上,我們可以將長方體C的長為2d的兩條邊分別3等分和4等分,將它的長為d的邊2等分, 由此導(dǎo)出24個大小

10、相等的( d /2) ( d /2) (2d /3) 的小長方體. 如圖3所示:若長方體C中有多于24個S中的點,則由鴿舍原理易知至少有一個( d /2) ( d /2) (2d /3) 的小長方體中有2個以上S中的點. 設(shè)u, v是這樣2個點,它們位于同一小長方體中, distance ( u, v)22222221817)3/2()2/()2/()()()()()()(ddddvzuzvyuyvxux為了確切地知道對于P1 中每個點p最多檢查P2 中的哪24個點,我們可以將點p和P2 中所有S2的點投影到平面P: y = m上. 由于能與p點一起構(gòu)成最接近點對候選者的S2 中點一定在長方體

11、R中,所以它們在平面P上的投影點與點p在P上投影點的距離小于d. 由上面的分析可知, 這種投影點最多只有24個. 因此,若將P1 和P2 中所有S的點依次按其x坐標(biāo)和z坐標(biāo)排好序,則對P1 中任意點p而言,對已經(jīng)按照x坐標(biāo)和z坐標(biāo)排好序的點列作一次線性掃描,就可以找出所有最接近點對的候選者. 設(shè)點q ( x, y, z) 為P2 中可以與P1 中的一點p ( x0 , y0 , z0 ) 構(gòu)成候選點對的排好序的24個點中的一點,則滿足x ( x0 - d, x0 + d) , z ( z0 - d, z0 +d) ,即投影點在以p的投影點為中心的2d 2d的正方形區(qū)域中的點是我們要考察的候選點

12、. 這就意味著我們可以在O ( n) 時間內(nèi)完成分治法的合并步驟.如何確定要檢查哪24個點？double spair (S ) n =| S | ; /| S | 表示S中點的個數(shù)3 /if ( n 2) return ;1. m = S中各點y坐標(biāo)的中位數(shù);利用平面P: y = m 劃分構(gòu)造子集S1 和S2 ;S1 = p S | y ( p) m 2. d1 = spair (S1 ) ; d2 = spair (S2 ) ;3. dm = min ( d1 , d2 ) ;4. 設(shè)P1 是S1 中距垂直分割面P的距離在dm之內(nèi)的所有點組成的集合; P2 是S2 中距垂直分割面的距離在dm 之內(nèi)的所有點組成的集合; 將P1 和P2 中點依其依次按照其x坐標(biāo)值和z坐標(biāo)值排序; 并設(shè)X1、X2 是P1、P2 依據(jù)x坐標(biāo)值排好序的點列; Z1、Z2 是X1、X2 再 依據(jù)z坐標(biāo)值排好