最接近點(diǎn)對(duì)問(wèn)題

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

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

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

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

5、有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。對(duì)選者。對(duì)P1中每一點(diǎn)最多只要檢查中每一點(diǎn)最多只要檢查P2中排好中排好序的相繼序的相繼6個(gè)點(diǎn)。個(gè)點(diǎn)。如何確定要檢查哪6個(gè)點(diǎn)double cpair2(S) n=|S|; if (n 2) return ;1、m=S中各點(diǎn)中各點(diǎn)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中距垂直分割線(xiàn)中距垂直分割線(xiàn)l的距離在的距離在dm之之內(nèi)的所有點(diǎn)組成

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

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

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

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

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

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

12、. 這就意味著我們可以在O ( n) 時(shí)間內(nèi)完成分治法的合并步驟.如何確定要檢查哪24個(gè)點(diǎn)？double spair (S ) n =| S | ; /| S | 表示S中點(diǎn)的個(gè)數(shù)3 /if ( n 2) return ;1. m = S中各點(diǎn)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)的所有點(diǎn)組成的集合; P2 是S2 中距垂直分割面的距離在dm 之內(nèi)的所有點(diǎn)組成的集合; 將P1 和P2 中點(diǎn)依其依次按照其x坐標(biāo)值和z坐標(biāo)值排序; 并設(shè)X1、X2 是P1、P2 依據(jù)x坐標(biāo)值排好序的點(diǎn)列; Z1、Z2 是X1、X2 再 依據(jù)z坐標(biāo)值排好