三維空間最接近點問題

問題：給定平面上n個點，找其中的一對點，使得在n個點所組成的所有點對中，該點對間的距離最小。說明：嚴格來講，最接近點對可能多于一對，為簡便起見，我們只找其中的一對作為問題的解。一個簡單的做法是將每一個點與其他n-1個點的距離算出，找出最小距離的點對即可。該方法的時間復雜性是T(n)=n(n-1)/2+n=O(n2)，效率較低。已經證明，該算法的計算時間下界是Ω(nlogn)。分治法解決二維空間最接近點問題選取一垂直線l:x=m來作為分割直線。其中m為S中各點x坐標的中位數(shù)。由此將S分割為S1和S2。遞歸地在S1和S2上找出其最小距離d1和d2，并設d=min{d1,d2}，S中的最接近點對或者是d，或者是某個{p,q}，其中p∈S1且q∈S2。第一步篩選：如果最近點對由S1中的p3和S2中的q3組成，則p3和q3一定在劃分線L的距離d內。第二步篩選：考慮P1中任意一點p，它若與P2中的點q構成最接近點對的候選者，則必有distance(p，q)＜d。滿足這個條件的P2中的點一定落在一個d×2d的矩形R中R中的點具有稀疏性P2中任何2個S中的點的距離都不小于d。由此可以推出矩形R中最多只有6個S中的點。在分治法的合并步驟中最多只需要檢查6×n/2=3n個候選點對！R中最多只有6個S中的點證明:將矩形R的長為2d的邊3等分，將它的長為d的邊2等分，由此導出6個(d/2)×(2d/3)的矩形。若矩形R中有多于6個S中的點，則由鴿舍原理易知至少有一個(d/2)×(2d/3)的小矩形中有2個以上S中的點。設u，v是位于同一小矩形中的2個點，則distance(u,v)<d。這與d的意義相矛盾。*鴿舍原理（也稱抽屜原理）把n+1個球，放入n個抽屜，則一定有一個抽屜內至少有2個球。P2中與點p最接近這6個候選點的縱坐標與p的縱坐標相差不超過d.因此，若將P1和P2中所有S中點按其y坐標排好序，則對P1中所有點，對排好序的點列作一次掃描，就可以找出所有最接近點對的候選者。對P1中每一點最多只要檢查P2中排好序的相繼6個點。如何確定要檢查哪6個點doublecpair2(S){n=|S|;if(n<2)return;1、m=S中各點x間坐標的中位數(shù);

構造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、設P1是S1中距垂直分割線l的距離在dm之內的所有點組成的集合；

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

if(n<2)return∞;1.m=S中各點y坐標的中位數(shù);利用平面P:y=m劃分構造子集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.設P1是S1中距垂直分割面P的距離在dm之內的所有點組成的集合;P2是S2中距垂直分割面的距離在dm之內的所有點組成的集合;將P1和P2中點依其依次按照其x坐標值和z坐標值排序;并設X1、X2是P1、P2依據x坐標值排好序的點列;Z1、Z2是X1、X2再依據z坐標值排好序的點列