對(duì)分治法解決三維最近點(diǎn)對(duì)問題的優(yōu)化

李俊杰，樓吉林

（浙江農(nóng)林大學(xué)暨陽學(xué)院，諸暨 311800）

0 引言

三維最近點(diǎn)對(duì)問題，是指如何在三維坐標(biāo)系中找出一對(duì)距離最近的點(diǎn)。該問題是計(jì)算機(jī)算法、計(jì)算幾何中的經(jīng)典問題，在圖像處理、空中交通管制、智能交通、化學(xué)反應(yīng)、物理變化、材質(zhì)檢測、天文觀測等領(lǐng)域都有廣泛應(yīng)用，確定性算法可以達(dá)到O（nlogn）的時(shí)間復(fù)雜度[1]。

三維最近點(diǎn)對(duì)問題可以描述為：在空間集合S中，存在n個(gè)點(diǎn)依次記為P1，P2，...，Pn（n≥3）。其中任意的Pi與Pj（j≠i）組成一個(gè)點(diǎn)對(duì)，該點(diǎn)對(duì)距離記為dij，求所有點(diǎn)對(duì)距離中的最小距離dmin=min{dij（Pi，Pj）|Pi∈S，Pj∈S}。由Pi和Pj所組成的最近點(diǎn)對(duì)可能多于一對(duì)，本文只討論如何求出一對(duì)點(diǎn)對(duì)的情況。

1 問題分析

在解決三維最近點(diǎn)對(duì)問題之前，我們可以通過二維最近點(diǎn)對(duì)問題的算法來進(jìn)行類比，第一步采用分治法對(duì)空間進(jìn)行劃分。例如，在三維坐標(biāo)系V中，存在n個(gè)點(diǎn)依次記為P1，P2，...，Pn（n≥3），為了將這n個(gè)點(diǎn)盡可能均勻的劃分到兩個(gè)空間V1和V2中，可以先計(jì)算點(diǎn)集中各點(diǎn)x軸的中位數(shù)，并構(gòu)造一個(gè)垂直于x軸的平面x（P）=k來作為分割平面[2]。其中空間V1={x（Pi）≤kx|Pi∈V，k∈N}，V2={x（Pj）>kx|Pj∈V，k∈N}。通過遞歸算法，計(jì)算出V1和V2中的最小點(diǎn)對(duì)距離的d1和d2，令dm=min{d1，d2}。

第二步同樣類比二維情況，求出dl=min{dij（Pi，Pj）|Pi∈V1，Pj∈V2}，即在 V1 與 V2 中各取一點(diǎn)，所組成的最近點(diǎn)對(duì)距離。其方法是：在第一次進(jìn)行分割的原分割面kx的基礎(chǔ)上做兩個(gè)與之平行的切面x1=kx+dm與x2=kx-dm（k∈N），將屬于兩切面之間的點(diǎn)按照z軸坐標(biāo)進(jìn)行排序。故屬于x1≤xi≤kx范圍內(nèi)的點(diǎn)Pi（xi，yi，zi）所能組成最短距離的另一個(gè)端點(diǎn)Pj（xj，yj，zi）一定存在以下關(guān)系：kx≤xj≤x2；同時(shí)易知，與 Pi組成最近點(diǎn)對(duì)的另一端點(diǎn)Pj一定在以Pi為球心，以dm為半徑的半球面內(nèi)，即{sqrt（（xi-xj）2+（yi-yj）2+（zi-zj）2）≤dm|xj>xi}。故只要找出上述兩式的集合，即可得出需要進(jìn)行判別的端點(diǎn)Pj所屬的范圍。但由于計(jì)算機(jī)進(jìn)行上述操作所耗費(fèi)的時(shí)間遠(yuǎn)遠(yuǎn)大于預(yù)期，以至于不能直接進(jìn)行運(yùn)算，于是需要采用更加巧妙的方法。不難發(fā)現(xiàn)，Pi和Pj中的點(diǎn)具有以下稀疏的性質(zhì)[3]：對(duì)于Pi中的任意一點(diǎn)，Pj中的點(diǎn)必定落在一個(gè)dm*2dm*2dm的長方體中。從上述分析可以想到利用該半球面的外接長方體（dm*2dm*2dm）來代替球面進(jìn)行判斷，來減小計(jì)算量。隨后，只要逐次比較kx≤xj≤x2空間與該外接長方體空間的交集空間內(nèi)的所有點(diǎn)即可得到以Pi，Pj為端點(diǎn)的最短距離。

不過，直接利用外接長方體對(duì)Pj進(jìn)行篩選，會(huì)造成少量多余的計(jì)算，每進(jìn)行一次距離運(yùn)算，則至少進(jìn)行了5次加法運(yùn)算與3次乘法運(yùn)算，增加了算法在時(shí)間上的消耗。那么根據(jù)硬件的實(shí)現(xiàn)原理，如果可以將一部分的乘法運(yùn)算轉(zhuǎn)化成運(yùn)算速度更快的加法運(yùn)算，則能夠在一定程度上提升算法效率。如圖1所示。

圖1 點(diǎn)Pi判別空間的切割圖

對(duì)半球面的外接長方體進(jìn)行切割，四個(gè)切割面用虛線表示（圖中只給出了兩個(gè)）分別為可以看出，四個(gè)切割面以外的空間是不需要進(jìn)行計(jì)算的。令時(shí)，待運(yùn)算的點(diǎn)Pj可以直接排除。由于鴿舍原理，在未進(jìn)行切割時(shí)dm*2dm*2dm的長方體中最多僅能存在24個(gè)滿足條件的點(diǎn)[3]。通過計(jì)算可以得到未切割時(shí)所求長方體體積為4dm3，所切割部分為圖2所示的陰影部分。

圖2 點(diǎn)Pi判別空間的切割面?zhèn)纫晥D

第三步，dmin=min（dl，dm）即為在三維坐標(biāo)系V中，這n個(gè)點(diǎn)所組成點(diǎn)對(duì)的最小距離。

2 算法設(shè)計(jì)

2.1 算法描述

通過上述的分析，可以得到分治法求三維最近點(diǎn)對(duì)函數(shù)Part3（）的偽代碼如下：

2.2 算法復(fù)雜度分析

在算法Part3的第一步中，進(jìn)行了查找各點(diǎn)x軸坐標(biāo)的中位數(shù)并進(jìn)行劃分的操作，易知時(shí)間復(fù)雜度為O（n）[3]。

第二步為遞歸運(yùn)算，滿足公式T（n）=2T（n/2）+O（n），n≥4，且假設(shè) n=2的 k次方，可證：

T（n）=2T（n/2）+O（n）

=2T（n/4）+2O（n/2）+O（n）

=...

=O（n）+O（n）+...+O（n）+O（n）+O（n）

=k*O（n）

=O（k*n）

=O（nlog2n）

即第二步算法的時(shí)間復(fù)雜度為O（n*logn）。

第三步為常數(shù)時(shí)間。

第四、五步在分治操作之前采用了預(yù)排序，對(duì)點(diǎn)集的y軸和z軸分別進(jìn)行了快排操作，可知時(shí)間復(fù)雜度為 O（n）。

第六步根據(jù)鴿舍原理可得，在判別空間內(nèi)最多只需要對(duì)有限的24個(gè)點(diǎn)進(jìn)行掃描，且在加入判斷條件的前提下，大約可以減少1/6的運(yùn)算量，因此此處的時(shí)間復(fù)雜度亦為O（n）。

第七步為常數(shù)時(shí)間。

綜上所述，該優(yōu)化算法整體的時(shí)間復(fù)雜度為O（n*logn），相較于經(jīng)典的三維最近點(diǎn)對(duì)算法，優(yōu)化的地方在于：將部分乘法運(yùn)算轉(zhuǎn)化成了加減法運(yùn)算，提升了端點(diǎn)在不同區(qū)域內(nèi)計(jì)算距離的速度；排除了距離運(yùn)算公式因重復(fù)進(jìn)行迭代法而產(chǎn)生的時(shí)間冗余，減少了距離計(jì)算所耗費(fèi)的時(shí)間。

[1]Shamos M I,Hoey D.Closest-Point Problems[C].Foundations of Computer Science,1975.Symposium on.IEEE,1975:151-162.

[2]胡金初.空間最近點(diǎn)對(duì)的計(jì)算機(jī)算法研究[J].計(jì)算機(jī)科學(xué)，2008,35（1）:233-235.

[3]王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析[M].電子工業(yè)出版社，2012.