三維空間的最接近點對問題

1、 三維空間的最接近點對問題 劉志輝 (中國民航大學 天津300300) 摘要：最接近點對問題的求解就是在點集空間中求解最接近的一對點的距離。 本 文利用分治策略并結合預排序和分層映射技術把一維、二維情況下的最接近點對 問題推廣至三維，使問題在 O(n*logn)O(n*logn)時間內(nèi)得以解決，相對時間復雜度為 O(n2)的普通方法而言，效率得到很大的提高。 關鍵詞：最接近點對；鴿舍原理；分層映射； 在文獻1中，對一維和二維情況下的最接近點問題的求解進行了詳細描述， 于是引起了人們對三維情況下的最接近點對問題的關注。文獻 2中，提出了一 種對三維最接近點對問題的求解方法： 先對三維空間的點集進

2、行兩次預排序， 利 用與二維情況下相類似的合并算法， 在 O(n* log n)O(n* log n)時間內(nèi)求出最接近的點對。但 是其合并過程所采用的算法不明確， 令人質(zhì)疑。本文只需對空間點集進行一次預 排序，然后在合并過程中采用分層映射技術使其在 O(n)O(n)的時間內(nèi)完成合并，從 而整個算法的時間復雜度為 O(nMogn),O(nMogn),并且算法思路清晰?？梢宰C明在漸近意 義下，此算法已是最優(yōu)算法。 一、一維和二維情況下的最接近點對問題 把一維情況下點集 S S 中的n個點退化為x軸上的n個實數(shù)x1,x2，,xn。于是最 接近點對即為這n個實數(shù)中相差最小的兩個實數(shù)。顯然可以先將這 n

3、個實數(shù)排序 好，映射到x軸上，然后用x軸上某個點m將 S S 劃分為大小大致相等的兩個子集 合和S2,且S1 =1xw S|x mL如圖1所示。于是求 S S 中 的最接近點對轉(zhuǎn)變?yōu)榉謩e求、S2中的最接近點對和其合并后的最接近點對。 如果已求得和S2中的最小點對距離分別為 4 4 和d2,合并時只需 0(1)0(1)時間就能 求得合并時的最接近點對，即 S和S2中分別離點m最近的一個點，如圖1中的 點Pm和qm。這樣 S S 中的最接近點對的距離為d =maxQi,d2,| Pm -qm。從而一 維情況下只需用一次線性掃描就可以找出最接近點對，算法中主要計算時間花費 在排序上，總的時間為 o(

4、n*log n)o(n*log n)。 p q 圖i 一維情況的最接近點對分治法 二維情況下的最接近點對可以表述為求 x y y 平面中最接近的點對。先對平面 中所有點按照x坐標進行排序，用 S S 記排序后的點集，求出所有點x坐標值的中 位數(shù)，記為 m m , ,然后用直線 l l : : x = mx = m 把點集 S S 劃分為大致相等的兩個子集 S S 和 S S2 , 且G =pw S|x(p) Mm； S2 =pw S|x(p) m。這樣把求 S S 中的最接近點對轉(zhuǎn)變 為分別求S、S2中的最接近點對和其合并后的最接近點對。子集中的最接近點 對可以遞歸求得，但合并時最接近點對的求

5、解比一維情況下要復雜些。 設di和d2 分別為S1和S2中的最小距離，設d = minQ1, d2 。在合并時，對于 S S 中距離小于 d d 的兩點 p p 和 q q 必定滿足：p p 和 q q 分別屬于 S S 和 S S , ,在此設 pS, qSpS, qS；令 R R 和 P2分別表示距直線 l l 的左邊和右邊的寬為 d d 的兩個區(qū)間，那么pw p , qw p2,如圖 2左所示。按照正常思維，Pi中的所有點和P2中的所有點在最壞情況下有 n n2/4/4 對 最接近點對的候選者，但是 Pi和耳中的點具有稀疏性質(zhì)，使得不必檢查所有這 n n2/ /4 4 個候選者，而最多只

6、需要檢查 6Mn/2=3n6Mn/2=3n 個候選者。Pi和巳中的點的稀疏 性表現(xiàn)在： 對于 R R 中的任意一點 p, P2p, P2中與其構成最接近點對的候選者的點必定 落在一個 d d 父 2d2d 的矩形 R R 中，如圖2左所示；利用鴿舍原理，R R 中這樣的候選點 最多只有6個，如圖2右所示，6個虛線矩形中每個矩形中最多只有一個候選點， 具體描述可以參考文獻1。因此，將Pi和巳和中所有中點按其坐標 y y 排好序， 那么對Pi中所有點最多只要檢查H中排好序的相繼6個點。但此時合并的計算復雜 度需要 O(nO(n/ /ogn)ogn), ,并不是 O(n)O(n), ,沒有到達預想的

7、效果，不過可以通過在求解 問題之前，把 S S 中的點按其坐標 y y 進行預排序來解決。所以二維情況下的最接近 點對可以在的 O(n*log n)O(n*log n)時間內(nèi)求得。 T 2d/3 F 2d/3 r k 2d/3 F - - H d/2 d/2 圖2二維情況的最接近點對分治法 二、最接近點對問題的三維推廣 有了一維和二維的最接近點對描述，可以依此推廣到三維。對于三維空間， 所有的點有 xyzxyz 三個坐標。于是三維情況下的最接近點對可以表述為求 xyzxyz 空間中 最接近的點對。 1、問題描述 先對三維空間中所有點按照 y y 坐標進行排序，用 S S 記排序后的點集。求出所

8、 有點y y 坐標值的中位數(shù)，記為 m,然后用平面 l l ： y = m m 把點集 S S 劃分為大致相等 的兩個子集S和$ ,且S =w S|y(p) Mmh S2 =%亡S|y(p) Am)。這樣把求 S S 中的最接近點對轉(zhuǎn)變?yōu)榉謩e求 、S2中的最接近點對和其合并后的最接近點 對。然后依此方法遞歸地在Si和&中求解最接近點對，設di和d2分別為S和8 中的最小距離，設d =mindi,d20但求解合并時最接近點比照一維和二維都要 復雜得多，成為問題求解的難點。 合并時，對于 S S 中距離小于 d d 的兩點 p p 和 q q 必定滿足：p p 和 q q 分別屬于 S S

9、 和 S2 ,在此設pw S| , qw S2。那么 p p 和 q q 距平面的距離均小于 d d 。因此，假設令耳和 P2分別表示距平面l的左邊和右邊的寬為d的兩個長條形區(qū)間，那么pw R , qw P2 , 如圖Pi P2 d r i d 3左所示。此時，P1中的所有點和P2中的所有點在最壞情況下有 n n2/4/4 對最 接近點對的候選者。但是P和P2中的點與二維情況下具有類同的稀疏性質(zhì)， 使得 不必檢查所有這 n n2 / 4/ 4 個候選者。R和P2中的點的稀疏性表現(xiàn)在：對于 P中的任 意一點 p p , , P2中與其構成最接近點對的候選者的點必定落在一個 d d 父 2dM 2

10、d2dM 2d 的長 方體 R R 中，如圖3左所示；利用鴿舍原理，R R 中這樣的候選點最多只有24個2, 如圖3右所示，24個虛線小長方體中每個長方體中最多只有一個候選點。因為 對于如圖3右中，每一個小長方體(d/2)M(2d/3)d/2)(d/2)M(2d/3)d/2)中如果有2個以上 S S 中 的點，設u和v是這樣的2個點，那么 2 2 2 1717 2 (x(u)(x(u)- -x(v)x(v) (y(u)(y(u)- -y(v)y(v) (z(u(z(u) )- -z(v) =.dz(v) =.d 因此，dist(u,v) d ,dist(u,v) d ,這與前面 d d 的意義

11、相矛盾。也就是說長方體 R R 中最多 只有24個 S S 中的點，其實數(shù)字24并不重要，重要的是長方體 R R 中最多只有常數(shù) 個這樣的點。因此，在分治法的合并過程中，最多只需要檢查 24wn/2 = 12n24wn/2 = 12n 個 候選者，而不 n n2/4/4 個候選者。在此并不能意味著可以在 O(n)O(n)時間內(nèi)完成分治法 的合并過程，因為對于P中的任意一點，我們并不確切知道要檢查 巳中哪24個 點。 C 圖3 三維情況的最接近點對分治法 2、分層映射和預排序 為了解決以上合并過程中遇到的問題，在2中先將P和巳中的所有點按其x 坐標排好序，然后對排好序的Pi和P2再進行z坐標排序

12、，也就是在此進行兩次排 序。令 經(jīng)過這樣的兩次排序后， 日和H變?yōu)閆i和Z2。這時對于乙中的每一點最 多只要檢查Z2中的相繼24個點，因此對于乙中所有點，作一次掃描，就可以在 Z2中找出所有最接近點對的候選者。但這種方法令人質(zhì)疑，且要經(jīng)過兩次排序， 在空間點數(shù)很大時，效率提高得不明顯。 相對上面的缺乏，分層映射顯出了它的優(yōu)越性。在合并時，先對于P和P2中 的所有點順z軸方向分層映射到長為 2d2d 的長條形區(qū)域內(nèi)，然后分別對各層中 p 和P2中的點按其x坐標排序。接著對每一層中排好序的R中的點只需檢查同層中 排好序的月中的相繼24個點，因此對于排好序的P中所有點，逐層掃描，通過 一次掃描，就可

13、以在排好序的P2中找出所有最接近點對的候選者。具體的分層映 射過程為：找出P和P2的合集中z坐標值最小的點o；從o點開始，順著z軸， 每間距 2d2d 作一平行于xoyxoy 面的分割面，如此分割到P,和巳的合集中z坐標值最大 的點或包括z坐標值最大的點終止。這時，p和耳中的所有點就分別被映射到分 割的長條形區(qū)域中，每一層可以用一個數(shù)組來保存所映射的點集。 在此還要注意 一個問題，在前面討論 P Pi和巳中的點的稀疏性質(zhì)時，要求對于 P P 中的任意一點 p, Bp, B 中與其構成最接近點對的候選者的點必定落在以從 p p 點引出的一條垂直于分 割平面 l l 的直線為中心軸的一個 d d

14、父 2dM 2d2dM 2d 的長方體 R R 中，而P1中的點并不能保 證都位于每一層的中平面上，所以對于每層中非中心平面上的 P中的點，還必須 要投影到相鄰的分割層中。投影的原那么為：中心平面以上的點投影到與該層上相 鄰的分割層中；中心平面以下的點投影到與該層下相鄰的分割層中。 很容易發(fā)現(xiàn)，采用以上分層映射技術和排序的方法來完成合并， 在最壞情況 下其計算復雜度需要 O(n*log n)O(n*log n), ,并不是 O(n)O(n), ,因此這種效果是不理想的。產(chǎn) 生原因就在于排序時消耗了 O(n*logn)O(n*logn)的時間。這時我們可以采用二維情況下的 最接近點對的預排序技術

15、來降低合并時排序所消耗的不必要的時間， 使合并在的 O(n)O(n)時間內(nèi)完成，即在問題求解之前對中的所有點進行一次 x坐標預排序。 3、分層軸的選取 對于三維情況下的最接近點對問題的求解還牽涉到一個分層軸的選取過程。 令 V V 為包含三維空間中所有點的最小邊界長方體，dx為 V V 在x軸方向的長度，dy 為 V V在 y y 軸方向的長度，dz為 V V 在z軸方向的長度。那么選取minQx,dy,dz的方 向軸為分層軸，這樣有利于減少分層層次，降低分層的時空開銷。對于dx、dy和 dz值差不多的情況，任意選取一個坐標軸作為分層軸。 4、算法偽代碼描述 結合以上描述，用分治法求三維點集最

16、接近點對的算法 Cpair3如下： bool Cpair(S,d) n=|S|； if(n2) d=二; return false; SelestAxis(S,x,y,z); /選取分層軸，在此設選取的分層軸為 Z軸 X=SortX(S); /對S中所有點進行X坐標排序 Y=SortY(S); /對S中所有點進行Y坐標排序 Cpair(X,Y,d,n); return true; void Cpair(X,Y,d,n) if(n2) d二二； return ; m=Y中各點y坐標的中位數(shù)； 構造 Yi 和 Y2; YI = p w Y | y( p) W m,Y2 = p w Y | y(p)

17、 a m Cpair(X,Yi,di,n/2); Cpair(X,Y2,d2,n-n/2); dm=min(di, d2); 結合預排序X,構造Pi和P2,并對Pi和P2中所有點順Z軸進行分層映射； /P -；p Yi |y(p) -m| dmP2 -.p Y2 11y(p)-m| dm) 逐層掃描每一層，對每層中Pi中的每個點檢查同層的P2中與其距離在dm 之內(nèi)的所有點； 按照上述掃描方式找到的最近點對的距離 dn； d=mind m,dn; 5、算法效率 由前面的問題描述可知，整個問題的求解過程需要兩次排序， 一次用于分治 劃分，一次用于合并時的點對掃描，所以用于排序的時間為 O(nSogn)O(nSogn)。由于在 合并過程中消耗時間為 O(n),O(n),因此用分治法求解問題所消耗的時間 T(n)T(n) 可 以 用 下式表達: O(i) T(n)=， 2T(n/2)+O(n) 計算得出 T(n) = O(nlogn),T(n) = O(nlogn),結合排序時所消耗的時間，整個算法可以在 O(n*log n)O(n*log n)時間內(nèi)完成。