三維空間的最接近點對問題劉志輝(中國民航大學天津300300)摘要：最接近點對問題的求解就是在點集空間中求解最接近的一對點的距離。本文利用分治策略并結合預排序和分層映射技術把一維、二維情況下的最接近點對問題推廣至三維，使問題在O(H*log/7)時間內得以解決，相對時間復雜度為O(/r)的普通方法而言，效率得到很大的提高。關鍵詞：最接近點對；鴿舍原理；分層映射；在文獻［1］中，對一維和二維情況下的最接近點問題的求解進行了詳細描述,于是引起了人們對三維情況下的最接近點對問題的關注。文獻［2］中，提出了一種對三維最接近點對問題的求解方法：先對三維空間的點集進行兩次預排序，利用與二維情況下相類似的合并算法，在O(7?*10gH)時間內求出最接近的點對。但是其合并過程所采用的算法不明確，令人質疑。本文只需對空間點集進行一次預排序，然后在合并過程中釆用分層映射技術使其在0(”)的時間內完成合并，從而整個算法的時間復雜度為O(72*10gH),并且算法思路清晰。可以證明在漸近意義下，此算法已是最優算法。一、一維和二維情況下的最接近點對問題把一維情況下點集S中的〃個點退化為X軸上的77個實數再,兀,...,￡。于是最接近點對即為這川個實數中相差最小的兩個實數。顯然可以先將這H個實數排序好，映射到X軸上，然后用X軸上某個點加將S劃分為大小大致相等的兩個子集合S］和S?,且Sl={xeS\x<m}；S2={xeS\x>tn},如圖1所示。于是求S中的最接近點對轉變為分別求二中的最接近點對和其合并后的最接近點對。如果已求得5和二中的最小點對距離分別為/和厶，合并時只需O⑴時間就能求得合并時的最接近點對，即乞和二中分別離點加最近的一個點，如圖1中的點幾和％。這樣S中的最接近點對的距離為d=imx{d”d2，|p,”-％|}。從而一維情況下只需用一次線性掃描就可以找出最接近點對，算法中主要計算時間花費在排序上，總的時間為O(7?*log/7)Oqn圖1一維情況的最接近點對分治法二維情況下的最接近點對可以表述為求xy平面中最接近的點對。先對平面中所有點按照x坐標進行排序，用S記排序后的點集，求出所有點x坐標值的中位數，記為加，然后用直線l:x=m把點集S劃分為大致相等的兩個子集$和二，且Sx={pgS|x(p)<m}；S2={peS\x(p)>m}0這樣把求S中的最接近點對轉變為分別求S、S,中的最接近點對和其合并后的最接近點對。子集中的最接近點對可以遞歸求得，但合并時最接近點對的求解比一維情況下要復雜些。設￡和厶分別為/和二中的最小距離，設〃=在合并時，對于S中距離小于d的兩點p和g必定滿足：p和q分別屬于S］和S),在此設pwS］,qeS2；令片和巴分別表示距直線/的左邊和右邊的寬為d的兩個區間，則pwR,qeP2t如圖2左所示。按照正常思維，片中的所有點和巴中的所有點在最壞情況下有用/4對最接近點對的候選者，但是片和匕中的點具有稀疏性質，使得不必檢查所有這滬/4個候選者，而最多只需要檢查6x77/2=3”個候選者。片和均中的點的稀疏性表現在：對于片中的任意一點p,巴中與其構成最接近點對的候選者的點必定落在一個dx2d的矩形R中，如圖2左所示；利用鴿舍原理，R中這樣的候選點最多只有6個，如圖2右所示，6個虛線矩形中每個矩形中最多只有一個候選點,具體描述可以參考文獻［1］。因此，將片和馬和中所有中點按其坐標y排好序，則對片中所有點最多只要檢查乙中排好序的相繼6個點。但此時合并的計算復雜

度需要O(Z7*log/0，并不是0(11),沒有達到預想的效果，不過可以通過在求解問題之前，把S中的點按其坐標y進行預排序來解決。所以二維情況下的最接近點對可以在的O(/?*log77)時間內求得。圖2二維情況的最接近點對分治法二、最接近點對問題的三維推廣有了一維和二維的最接近點對描述，可以依此推廣到三維。對于三維空間,所有的點有兀yz三個坐標。于是三維情況下的最接近點對可以表述為求卩乙空間中最接近的點對。1、問題描述先對三維空間中所有點按照y坐標進行排序，用S記排序后的點集。求出所有點y坐標值的中位數，記為加，然后用平面l:y=m把點集S劃分為大致相等的兩個子集S］和S.且Sj={pGSIy(p)<in}；S?={pwS|y(p)〉加}。這樣把求S中的最接近點對轉變為分別求S「二中的最接近點對和其合并后的最接近點對。然后依此方法遞歸地在乞和①中求解最接近點對，設/和▲分別為&和?中的最小距離，設〃=但求解合并時最接近點對比一維和二維都要復雜得多，成為問題求解的難點。

合并時，對于S中距離小于d的兩點p和g必定滿足：p和q分別屬于S］和S2,在此設pwS、,qeS2O那么p和?距平面的距離均小于d。因此，若令片和均分別表示距平面/的左邊和右邊的寬為d的兩個長條形區間，則peP^qeP29如圖3左所示。此時，片中的所有點和巴中的所有點在最壞情況下有滬/4對最接近點對的候選者。但是片和巴中的點與二維情況下具有類同的稀疏性質，使得不必檢查所有這滬/4個候選者。片和巴中的點的稀疏性表現在：對于片中的任意一點p,人中與其構成最接近點對的候選者的點必定落在一個dx2dx2d的長方體R中，如圖3左所示；利用鴿舍原理，R中這樣的候選點最多只有24個⑵,如圖3右所示，24個虛線小長方體中每個長方體中最多只有一個候選點。因為對于如圖3右中，每一個小長方體(d/2)x(2d/3)x(d/2)中如果有2個以上S中的點，設“和”是這樣的2個點，則17u(w)-x(v))2+(y(?)一y(y))2+(z(?)-z(y))2=—d2lo因此，dist(ii,v)<d,這與前面d的意義相矛盾。也就是說長方體R中最多只有24個S中的點，其實數字24并不重要，重要的是長方體R中最多只有常數個這樣的點。因此，在分治法的合并過程中，最多只需要檢查24x^2=12刃個候選者，而不滬/4個候選者。在此并不能意味著可以在O(n)時間內完成分治法的合并過程，因為對于片中的任意一點，我們并不確切知道要檢查巴中哪24個點0圖3三維情況的最接近點對分治法2、分層映射和預排序為了解決以上合并過程中遇到的問題，在［2］中先將呂和耳中的所有點按其x坐標排好序，然后對排好序的片和鬥再進行Z坐標排序，也就是在此進行兩次排序。令經過這樣的兩次排序后，片和人變為乙和乙。這時對于乙中的每一點最多只要檢查Z,中的相繼24個點，因此對于乙中所有點，作一次掃描，就可以在Z,中找出所有最接近點對的候選者。但這種方法令人質疑，且要經過兩次排序，在空間點數很大時，效率提高得不明顯。相對上面的不足，分層映射顯出了它的優越性。在合并時，先對于斥和出中的所有點順Z軸方向分層映射到長為2d的長條形區域內，然后分別對各層中片和巴中的點按其x坐標排序。接著對每一層中排好序的片中的點只需檢查同層中排好序的巴中的相繼24個點，因此對于排好序的片中所有點，逐層掃描，通過一次掃描，就可以在排好序的P,中找出所有最接近點對的候選者。具體的分層映射過程為：找出片和均的合集中z坐標值最小的點。；從。點開始，順著Z軸，每間距2d作一平行于xoy面的分割面，如此分割到片和人的合集中Z坐標值最大的點或包括Z坐標值最大的點終止。這時，片和人中的所有點就分別被映射到分割的長條形區域中，每一層可以用一個數組來保存所映射的點集。在此還要注意一個問題，在前面討論片和巴中的點的稀疏性質時，要求對于片中的任意一點P，均中與其構成最接近點對的候選者的點必定落在以從p點引出的一條垂直于分割平面/的直線為中心軸的一個dx2dx2d的長方體R中，而片中的點并不能保證都位于每一層的中平面上，所以對于毎層中非中心平面上的片中的點，還必須要投影到相鄰的分割層中。投影的原則為：中心平面以上的點投影到與該層上相鄰的分割層中；中心平面以下的點投影到與該層下相鄰的分割層中。很容易發現，釆用以上分層映射技術和排序的方法來完成合并，在最壞情況下其計算復雜度需要O(H*10gH),并不是0("),因此這種效果是不理想的。產生原因就在于排序時消耗了 的時間。這時我們可以采用二維情況下的最接近點對的預排序技術來降低合并時排序所耗費的不必要的時間，使合并在的0(”)時間內完成，即在問題求解之前對中的所有點進行一次X坐標預排序。3、 分層軸的選取對于三維情況下的最接近點對問題的求解還牽涉到一個分層軸的選取過程。令V為包含三維空間中所有點的最小邊界長方體，d,為V在X軸方向的長度，dy為V在y軸方向的長度，d：為V在z軸方向的長度。那么選取mill{<.,<.,<}的方向軸為分層軸，這樣有利于減少分層層次，降低分層的時空開銷。對于心、d,?和必值差不多的情況，任意選取一個坐標軸作為分層軸。4、 算法偽代碼描述結合以上描述，用分治法求三維點集最接近點對的算法Cpair3如下：boolCpair(S,d){n=|S|；if(n<2){d=co；returnfalse；}SelestAxis(S,x,y,z)； //選取分層軸，在此設選取的分層軸為Z軸X二SortX(S)； //對S中所有點進行X坐標排序Y二SortY(S)；//對S中所有點進行Y坐標排序Cpair(X,Y,d,n)；returntrue；voidCpair(X,Y,d,n)if(n<2){d=co；return；}m二Y中各點y坐標的中位數；構造￡和丫2； // ={pgrIy(p)<m},r2={peyIy(p)>m})Cpair(X,￡,d】,n/2)；Cpair(X,Y2,d2,n-n/2)；山二min(d「d2);結合預排序X,構造R和P2,并對R和P2中所有點順Z軸進行分層映射；//^= IIy(P)-^$d,”}，er2IIy(p)-m\><}逐層掃描每一層，對每層中R中的每個點檢查同層的P2中與其距離在d“之內的所有點；按照上述掃描方式找到的最近點對的距離d11；d=min{dai,dn};}5、算法效率由前面的問題描述可知，整個問題的求解過程需要兩次排序，一次用于分治劃分，一次用于合并時的點對掃描，所以用于排序的時間為O(n*log77)0由于在合并過程中消耗時間為0(71),因此用分治法求解問題所耗費的時間：TS)可以用下式表達：7V、回) ?<4T(7?)=27(/1/2)+O(h) n>4計算得岀T(/7)=0(H10gH),結合排序時所消耗的時間，整個算法可以在O(n*logn)時間內完成。三、總結三維情況下的最接近點對問題在日常