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

三維空間最接近點(diǎn)問(wèn)題

問(wèn)題：給定平面上n個(gè)點(diǎn)，找其中的一對(duì)點(diǎn)，使得在n個(gè)點(diǎn)所組成的所有點(diǎn)對(duì)中，該點(diǎn)對(duì)間的距離最小。說(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)題選取一垂直線l:x=m來(lái)作為分割直線。其中m為S中各點(diǎn)x坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=min{d1,d2}，S中的最接近點(diǎn)對(duì)或者是d，或者是某個(gè){p,q}，其中p∈S1且q∈S2。第一步篩選：如果最近點(diǎn)對(duì)由S1中的p3和S2中的q3組成，則p3和q3一定在劃分線L的距離d內(nèi)。第二步篩選：考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有distance(p，q)＜d。滿足這個(gè)條件的P2中的點(diǎn)一定落在一個(gè)d×2d的矩形R中R中的點(diǎn)具有稀疏性P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推出矩形R中最多只有6個(gè)S中的點(diǎn)。在分治法的合并步驟中最多只需要檢查6×n/2=3n個(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)的小矩形中有2個(gè)以上S中的點(diǎn)。設(shè)u，v是位于同一小矩形中的2個(gè)點(diǎn)，則distance(u,v)<d。這與d的意義相矛盾。*鴿舍原理（也稱抽屜原理）把n+1個(gè)球，放入n個(gè)抽屜，則一定有一個(gè)抽屜內(nèi)至少有2個(gè)球。P2中與點(diǎn)p最接近這6個(gè)候選點(diǎn)的縱坐標(biāo)與p的縱坐標(biāo)相差不超過(guò)d.因此，若將P1和P2中所有S中點(diǎn)按其y坐標(biāo)排好序，則對(duì)P1中所有點(diǎn)，對(duì)排好序的點(diǎn)列作一次掃描，就可以找出所有最接近點(diǎn)對(duì)的候選者。對(duì)P1中每一點(diǎn)最多只要檢查P2中排好序的相繼6個(gè)點(diǎn)。如何確定要檢查哪6個(gè)點(diǎn)doublecpair2(S){n=|S|;if(n<2)return;1、m=S中各點(diǎn)x間坐標(biāo)的中位數(shù);

構(gòu)造S1和S2；

//S1={p∈S|x(p)<=m},S2={p∈S|x(p)>m}2、d1=cpair2(S1);d2=cpair2(S2);3、dm=min(d1,d2);4、設(shè)P1是S1中距垂直分割線l的距離在dm之內(nèi)的所有點(diǎn)組成的集合；

P2是S2中距分割線l的距離在dm之內(nèi)所有點(diǎn)組成的集合；將P1和P2中點(diǎn)依其y坐標(biāo)值排序；并設(shè)X和Y是相應(yīng)的已排好序的點(diǎn)列；5、通過(guò)掃描X以及對(duì)于X中每個(gè)點(diǎn)檢查Y中與其距離在dm之內(nèi)的所有點(diǎn)(最多6個(gè))可以完成合并；當(dāng)X中的掃描指針逐次向上移動(dòng)時(shí)，Y中的掃描指針可在寬為2dm的區(qū)間內(nèi)移動(dòng)；設(shè)dl是按這種掃描方式找到的點(diǎn)對(duì)間的最小距離；6、d=min(dm,dl);returnd;}O(n)2T(n/2)常數(shù)時(shí)間O(n)常數(shù)時(shí)間O(n)復(fù)雜度分析①、⑤用了O(n)時(shí)間；②用了2T(n/2)時(shí)間③、⑥用了常數(shù)時(shí)間④在預(yù)排序的情況下用時(shí)O(n)選取一垂平面l:y=m來(lái)作為分割平面。其中m為S中各點(diǎn)y坐標(biāo)的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設(shè)d=min{d1,d2}，S中的最接近點(diǎn)對(duì)或者是d，或者是某個(gè){p,q}，其中p∈S1且q∈S2。分治法解決三維空間最接近點(diǎn)問(wèn)題第一步篩選：如果最近點(diǎn)對(duì)由S1中的p3和S2中的q3組成，則p3和q3一定在劃分平面L的距離d內(nèi)。第二步篩選：考慮P1中任意一點(diǎn)p，它若與P2中的點(diǎn)q構(gòu)成最接近點(diǎn)對(duì)的候選者，則必有distance(p，q)＜d。滿足這個(gè)條件的P2中的點(diǎn)定落在一個(gè)d×2d×2d的長(zhǎng)方體R中重要觀察結(jié)論：P2中任何2個(gè)S中的點(diǎn)的距離都不小于d。由此可以推出長(zhǎng)方體R中最多只有24個(gè)S中的點(diǎn)。在分治法的合并步驟中最多只需要檢24×n/2=12n個(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è)大小相等的(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)為了確切地知道對(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)方體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)列作一次線性掃描,就可以找出所有最接近點(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),則滿足x∈(x0-d,x0+d),z∈(z0-d,z0+d),即投影點(diǎn)在以p的投影點(diǎn)為中心的2d×2d的正方形區(qū)域中的點(diǎn)是我們要考察的候選點(diǎn).這就意味著我們可以在O(n)時(shí)間內(nèi)完成分治法的合并步驟.如何確定要檢查哪24個(gè)點(diǎn)？doublespair(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},S2={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)值排好序的點(diǎn)列