三維空間的最接近點(diǎn)對問題

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

2、但是其合并過程所采用的算法不明確，令人質(zhì)疑。本文只需對空間點(diǎn)集進(jìn)行一次預(yù)排序，然后在合并過程中采用分層映射技術(shù)使其在的時(shí)間內(nèi)完成合并，從而整個(gè)算法的時(shí)間復(fù)雜度為，并且算法思路清晰?？梢宰C明在漸近意義下，此算法已是最優(yōu)算法。一、一維和二維情況下的最接近點(diǎn)對問題把一維情況下點(diǎn)集中的個(gè)點(diǎn)退化為軸上的個(gè)實(shí)數(shù)。于是最接近點(diǎn)對即為這個(gè)實(shí)數(shù)中相差最小的兩個(gè)實(shí)數(shù)。顯然可以先將這個(gè)實(shí)數(shù)排序好，映射到軸上，然后用軸上某個(gè)點(diǎn)將劃分為大小大致相等的兩個(gè)子集合和，且；，如圖1所示。于是求中的最接近點(diǎn)對轉(zhuǎn)變?yōu)榉謩e求、中的最接近點(diǎn)對和其合并后的最接近點(diǎn)對。如果已求得和中的最小點(diǎn)對距離分別為和，合并時(shí)只需時(shí)間就能求得合并時(shí)的

3、最接近點(diǎn)對，即和中分別離點(diǎn)最近的一個(gè)點(diǎn)，如圖1中的點(diǎn)和。這樣中的最接近點(diǎn)對的距離為。從而一維情況下只需用一次線性掃描就可以找出最接近點(diǎn)對，算法中主要計(jì)算時(shí)間花費(fèi)在排序上，總的時(shí)間為。S2S1 m mpq圖1 一維情況的最接近點(diǎn)對分治法二維情況下的最接近點(diǎn)對可以表述為求平面中最接近的點(diǎn)對。先對平面中所有點(diǎn)按照坐標(biāo)進(jìn)行排序，用記排序后的點(diǎn)集，求出所有點(diǎn)坐標(biāo)值的中位數(shù)，記為，然后用直線把點(diǎn)集劃分為大致相等的兩個(gè)子集和，且；。這樣把求中的最接近點(diǎn)對轉(zhuǎn)變?yōu)榉謩e求、中的最接近點(diǎn)對和其合并后的最接近點(diǎn)對。子集中的最接近點(diǎn)對可以遞歸求得，但合并時(shí)最接近點(diǎn)對的求解比一維情況下要復(fù)雜些。設(shè)和分別為和中的最小距離，

4、設(shè)。在合并時(shí)，對于中距離小于的兩點(diǎn)和必定滿足：和分別屬于和，在此設(shè)，；令和分別表示距直線的左邊和右邊的寬為的兩個(gè)區(qū)間，則，如圖2左所示。按照正常思維，中的所有點(diǎn)和中的所有點(diǎn)在最壞情況下有對最接近點(diǎn)對的候選者，但是和中的點(diǎn)具有稀疏性質(zhì)，使得不必檢查所有這個(gè)候選者，而最多只需要檢查個(gè)候選者。和中的點(diǎn)的稀疏性表現(xiàn)在：對于中的任意一點(diǎn)，中與其構(gòu)成最接近點(diǎn)對的候選者的點(diǎn)必定落在一個(gè)的矩形中，如圖2左所示；利用鴿舍原理，中這樣的候選點(diǎn)最多只有6個(gè)，如圖2右所示，6個(gè)虛線矩形中每個(gè)矩形中最多只有一個(gè)候選點(diǎn)，具體描述可以參考文獻(xiàn)1。因此，將和和中所有中點(diǎn)按其坐標(biāo)排好序，則對中所有點(diǎn)最多只要檢查中排好序的相繼6

5、個(gè)點(diǎn)。但此時(shí)合并的計(jì)算復(fù)雜度需要，并不是，沒有達(dá)到預(yù)想的效果，不過可以通過在求解問題之前，把中的點(diǎn)按其坐標(biāo)進(jìn)行預(yù)排序來解決。所以二維情況下的最接近點(diǎn)對可以在的時(shí)間內(nèi)求得。d/2d/22d/32d/32d/3P1P2ddddRp圖2二維情況的最接近點(diǎn)對分治法二、最接近點(diǎn)對問題的三維推廣有了一維和二維的最接近點(diǎn)對描述，可以依此推廣到三維。對于三維空間，所有的點(diǎn)有三個(gè)坐標(biāo)。于是三維情況下的最接近點(diǎn)對可以表述為求空間中最接近的點(diǎn)對。1、 問題描述先對三維空間中所有點(diǎn)按照坐標(biāo)進(jìn)行排序，用記排序后的點(diǎn)集。求出所有點(diǎn)坐標(biāo)值的中位數(shù)，記為，然后用平面把點(diǎn)集劃分為大致相等的兩個(gè)子集和，且；。這樣把求中的最接近點(diǎn)

6、對轉(zhuǎn)變?yōu)榉謩e求、中的最接近點(diǎn)對和其合并后的最接近點(diǎn)對。然后依此方法遞歸地在和中求解最接近點(diǎn)對，設(shè)和分別為和中的最小距離，設(shè)。但求解合并時(shí)最接近點(diǎn)對比一維和二維都要復(fù)雜得多，成為問題求解的難點(diǎn)。合并時(shí)，對于中距離小于的兩點(diǎn)和必定滿足：和分別屬于和，在此設(shè)，。那么和距平面的距離均小于。因此，若令和分別表示距平面的左邊和右邊的寬為的兩個(gè)長條形區(qū)間，則，如圖3左所示。此時(shí)，中的所有點(diǎn)和中的所有點(diǎn)在最壞情況下有對最接近點(diǎn)對的候選者。但是和中的點(diǎn)與二維情況下具有類同的稀疏性質(zhì)，使得不必檢查所有這個(gè)候選者。和中的點(diǎn)的稀疏性表現(xiàn)在：對于中的任意一點(diǎn)，中與其構(gòu)成最接近點(diǎn)對的候選者的點(diǎn)必定落在一個(gè)的長方體中，如圖

7、3左所示；利用鴿舍原理，中這樣的候選點(diǎn)最多只有24個(gè)2，如圖3右所示，24個(gè)虛線小長方體中每個(gè)長方體中最多只有一個(gè)候選點(diǎn)。因?yàn)閷τ谌鐖D3右中，每一個(gè)小長方體中如果有2個(gè)以上中的點(diǎn)，設(shè)和是這樣的2個(gè)點(diǎn)，則 因此，這與前面的意義相矛盾。也就是說長方體中最多只有24個(gè)中的點(diǎn)，其實(shí)數(shù)字24并不重要，重要的是長方體中最多只有常數(shù)個(gè)這樣的點(diǎn)。因此，在分治法的合并過程中，最多只需要檢查個(gè)候選者，而不個(gè)候選者。在此并不能意味著可以在時(shí)間內(nèi)完成分治法的合并過程，因?yàn)閷τ谥械娜我庖稽c(diǎn)，我們并不確切知道要檢查中哪24個(gè)點(diǎn)。圖3三維情況的最接近點(diǎn)對分治法2、 分層映射和預(yù)排序?yàn)榱私鉀Q以上合并過程中遇到的問題，在2中先

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

9、有最接近點(diǎn)對的候選者。具體的分層映射過程為：找出和的合集中坐標(biāo)值最小的點(diǎn)；從點(diǎn)開始，順著軸，每間距作一平行于面的分割面，如此分割到和的合集中坐標(biāo)值最大的點(diǎn)或包括坐標(biāo)值最大的點(diǎn)終止。這時(shí)，和中的所有點(diǎn)就分別被映射到分割的長條形區(qū)域中，每一層可以用一個(gè)數(shù)組來保存所映射的點(diǎn)集。在此還要注意一個(gè)問題，在前面討論和中的點(diǎn)的稀疏性質(zhì)時(shí)，要求對于中的任意一點(diǎn)，中與其構(gòu)成最接近點(diǎn)對的候選者的點(diǎn)必定落在以從點(diǎn)引出的一條垂直于分割平面的直線為中心軸的一個(gè)的長方體中，而中的點(diǎn)并不能保證都位于每一層的中平面上，所以對于每層中非中心平面上的中的點(diǎn)，還必須要投影到相鄰的分割層中。投影的原則為：中心平面以上的點(diǎn)投影到與該層

10、上相鄰的分割層中；中心平面以下的點(diǎn)投影到與該層下相鄰的分割層中。很容易發(fā)現(xiàn)，采用以上分層映射技術(shù)和排序的方法來完成合并，在最壞情況下其計(jì)算復(fù)雜度需要，并不是，因此這種效果是不理想的。產(chǎn)生原因就在于排序時(shí)消耗了的時(shí)間。這時(shí)我們可以采用二維情況下的最接近點(diǎn)對的預(yù)排序技術(shù)來降低合并時(shí)排序所耗費(fèi)的不必要的時(shí)間，使合并在的時(shí)間內(nèi)完成，即在問題求解之前對中的所有點(diǎn)進(jìn)行一次坐標(biāo)預(yù)排序。3、 分層軸的選取對于三維情況下的最接近點(diǎn)對問題的求解還牽涉到一個(gè)分層軸的選取過程。令為包含三維空間中所有點(diǎn)的最小邊界長方體，為在軸方向的長度，為在軸方向的長度，為在軸方向的長度。那么選取的方向軸為分層軸，這樣有利于減少分層層

11、次，降低分層的時(shí)空開銷。對于、和值差不多的情況，任意選取一個(gè)坐標(biāo)軸作為分層軸。4、 算法偽代碼描述結(jié)合以上描述，用分治法求三維點(diǎn)集最接近點(diǎn)對的算法Cpair3如下：bool Cpair(S,d)n=|S|;if(n<2)d= ;return false;SelestAxis(S,x,y,z); /選取分層軸,在此設(shè)選取的分層軸為Z軸 X=SortX(S); /對S中所有點(diǎn)進(jìn)行X坐標(biāo)排序 Y=SortY(S); /對S中所有點(diǎn)進(jìn)行Y坐標(biāo)排序 Cpair(X,Y,d,n); return true;void Cpair(X,Y,d,n) if(n<2)d= ;return ;m=Y中各

12、點(diǎn)y坐標(biāo)的中位數(shù);構(gòu)造Y1和Y2; / , Cpair(X,Y1,d1,n/2); Cpair(X,Y2,d2,n-n/2); dm=min(d1, d2); 結(jié)合預(yù)排序X，構(gòu)造P1和P2，并對P1和P2中所有點(diǎn)順Z軸進(jìn)行分層映射; /, 逐層掃描每一層，對每層中P1中的每個(gè)點(diǎn)檢查同層的P2中與其距離在dm 之內(nèi)的所有點(diǎn); 按照上述掃描方式找到的最近點(diǎn)對的距離dn; d=mindm,dn;5、 算法效率由前面的問題描述可知，整個(gè)問題的求解過程需要兩次排序，一次用于分治劃分，一次用于合并時(shí)的點(diǎn)對掃描，所以用于排序的時(shí)間為。由于在合并過程中消耗時(shí)間為，因此用分治法求解問題所耗費(fèi)的時(shí)間可以用下式表達(dá)：計(jì)算得出，結(jié)合排序時(shí)所消耗的時(shí)間，整個(gè)算法可以在時(shí)間內(nèi)完成。三、總結(jié)三維情況下的最接近點(diǎn)對問題在日常生活中經(jīng)常遇到，特別是在民航的空中管制工作中。本文