對分治法解決三維最近點對問題的優化

2018-03-15 08:25:50李俊杰樓吉林

現代計算機 2018年3期

李俊杰，樓吉林

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

0 引言

三維最近點對問題，是指如何在三維坐標系中找出一對距離最近的點。該問題是計算機算法、計算幾何中的經典問題，在圖像處理、空中交通管制、智能交通、化學反應、物理變化、材質檢測、天文觀測等領域都有廣泛應用，確定性算法可以達到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軸的中位數，并構造一個垂直于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所屬的范圍。但由于計算機進行上述操作所耗費的時間遠遠大于預期，以至于不能直接進行運算，于是需要采用更加巧妙的方法。不難發現，Pi和Pj中的點具有以下稀疏的性質[3]：對于Pi中的任意一點，Pj中的點必定落在一個dm*2dm*2dm的長方體中。從上述分析可以想到利用該半球面的外接長方體（dm*2dm*2dm）來代替球面進行判斷，來減小計算量。隨后，只要逐次比較kx≤xj≤x2空間與該外接長方體空間的交集空間內的所有點即可得到以Pi，Pj為端點的最短距離。

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

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

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