李俊杰，樓吉林

（浙江農林大學暨陽學院，諸暨 311800）

0 引言

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

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

1 問題分析

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

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

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

圖1 點Pi判別空間的切割圖

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

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

第三步，dmin=min（dl，dm）即為在三維坐標系V中，這n個點所組成點對的最小距離。

2 算法設計

2.1 算法描述

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

2.2 算法復雜度分析

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

第二步為遞歸運算，滿足公式T（n）=2T（n/2）+O（n），n≥4，且假設 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）

即第二步算法的時間復雜度為O（n*logn）。

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

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

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

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

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

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

[2]胡金初.空間最近點對的計算機算法研究[J].計算機科學，2008,35（1）:233-235.

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