基于分治法的三維最近點對問題的研究

林澤瀚

（廣州大學 數學與信息科學學院，廣東廣州 510006）

0 引言

分治法在計算機科學領域中占據著重要的地位。這個思想被應用于多種重要的算法設計中，如快速排序、歸并排序、快速傅里葉算法等。最近點對問題是計算幾何領域的研究的重點問題，常常應用于大數據計算與空中交通的計算機自動控制系統中。目前，研究方向已經往高維空間下發展[1-5]。

本文所討論的問題可以描述為：給定個點，找出其中的一對點的距離，使得在這個點的所有點對中，該距離為所有點對中最小的。在實際情況中，可能會出現不止一個最近點對的情況，或者出現浮點誤差。為了規范化問題，我們只考慮得到在一定浮點誤差內準確的答案即可。

1 相關工作

1.1 二維最近點對樸素做法

（1）算法描述

對于二維最近點對的問題, 我們有樸素的做法: 維護一個最小值，直接對任意兩個點，檢驗它們是否能夠構成最小值，不斷更新答案，最終得到的就是最近點對距離。

（2）樸素做法的偽代碼表示

基于上文的分析，可以得到樸素做法的偽代碼如圖1所示：

圖1 樸素做法的偽代碼

（3）時間復雜度分析

分析上述算法,其中min函數是取兩者的最小值，distance函數是計算兩點的距離，即

兩個函數可以在O（1）的時間內完成，主要的時間復雜度來源于兩個循環的嵌套，設總的點數為n總的計算次數

根據上式，我們可以得出樸素做法求解二維最近點問題的時間復雜度是級別的。

1.2 二維最近點對分治做法

（1）算法描述

從分治的思想去考慮, 原問題可轉化為求[1,mid]和[mid+1,r]的最近點對。但是可能存在一個最近點對, 它的一個端點在[1,mid]，另一個端點在[mid+1,r]。所以,我們在分治的時候還需要對這種情況進行檢驗。我們先對點集按x坐標升序排序,當我們求得左右區間的最近點對距離d1和d2后 d=min(d1,d2)，在[1,r]中找到跟中間點point[mid]的x距離小于d的點集P3，這樣我們得到了候選點集P3。

實際上，我們得到的P3是一個以x=point[mid]。x為中軸線，長為2d, 寬為d的長方形，P3中的點集具有稀疏的特點(這一點我們稍后會用鴿巢原理證明)，我們對P3點集按y坐標排序,可以在常數級別的時間內做到對點集進行檢驗，得到當前的最近點對距離[6-8]。

（2）分治法的實現

基于以上的分析，我們得到二維最近點對分治做法的算法流程圖如圖2所示：

圖2 分治法求二維最近點對流程圖

（3）算法復雜度分析

由圖2可以看出，這個算法在“對點集按坐標排序，并檢驗每個點后面坐標距離不超過的點”這一步的時候涉及到兩層循環的嵌套，無法直觀分析出時間復雜度的級別，下面將對復雜度進行證明：

如圖3所示, 假設當前得到的最近點對距離為d,我們在某一遞歸過程中出現最近點對的兩個端點分別處于不同區域, 即一個端點屬于[1,mid]，另一個屬于[mid+1,r]，那么我們沿著中線mid畫出一個長2d, 寬d的小矩形區域, 對于這個矩形區域，很直觀地看出它由兩個邊長為d的正方形組成。顯然我們可以利用反證法和鴿巢原理證明小正方形中最多不會超過四個點[9-13]。

圖3 2d * d 的小矩形

這與d是當前的最近點對事實矛盾, 因此這個正方形區域的點不超過四個。

同理, 對于右邊的小正方形, 最多也只有四個點。那么總的矩形區域包含的點最多不會超過八個點。因此,我們在上述的二重循環中最多只會檢驗每個點之后的七個點,那么這個操作可以看做是在常數時間內完成的。于是,該算法的分割步驟和合并步驟總共耗時是O（n）的,x排序的耗時是O(nlogn), 而y對排序耗時為常數級別。

根據我們的分析, 算法耗費時間T（n）滿足遞歸方程

因此，我們上文提到的分治法求解二維最近點對問題的總體時間復雜度級別是O(nlogn)。

1.3 三維最近點對的樸素做法

（1）算法描述

當二維最近點對問題擴展到三維時，樸素做法的思路并沒有改變，此時只需改變函數的計算方式即可。

（2）時間復雜度分析

在復雜度方面，二維的樸素做法和三維的樸素做法區別在于函數，下面列出了函數在二維、三維下的形式：

顯然兩者在時間花費上都是O（1）的，那么時間復雜度方面和二維最近點對是一致的，都是O（n2）。

2 基于分治法的三維最近點對算法

2.1 三維最近點對O（n(logn)2）做法

二維空間下的最近點對問題能夠通過分治法改進優化，我們能否將這個算法推廣到三維的情況呢?還是那個思路, 在求1到n的最近點對問題,可以轉化為求[1,mid]到[mid+1,r]的最近點對。

（1）算法描述

我們先對點按x坐標排序, 此時可以截取一個平面x=mid，對于平面的左右部分分治, 找到左右兩端點集中最近距離d, 此時同樣有幾率會出現最近點對在分界面兩邊的情況, 比較難處理的是合并部分。 設左平面為P1,右平面為P2, 此時我們考慮做對點集按y坐標進行排序，并進行第二次分治——對y坐標進行分治。

第二次分治的時候，找到左右區間的最小值di, 并更新當前最小值d，此時已經轉換成平面內的最近點對問題，我們對點集進行z坐標排序后對每個點進行檢驗，不斷更新答案。

理論分析上，x,y,z坐標的地位是一致的，但是在實際情況中，由于數據的隨機性，并不一定是按x分治, 再按y坐標分治最優，可以根據實際情況調換分治策略，找范圍最小的一維作x分治[14,15]。

（2）算法的實現

基于上文的分析，我們可以給出兩次分治求解三維最近點對的算法流程圖如圖4所示。

圖4 兩次分治的流程圖

（3） 算法復雜度分析

對于x坐標進行分治的時候每個點在至多在logn個區間內被納入tmp，所以他至多參與logn次對y坐標的分治，而對y坐標的分治實際上就是二維下的平面最近點對問題，時間復雜度為O(nlogn)，所以總復雜度是O（n(logn)2）。

2.2 三維最近點對分治做法

（1） 算法描述

我們考慮位于平面x=mid左右兩端的點， 找出左端距離平面小于d的點加入到點集P1, 找出右端距離平面小于d的點加入到點集P2,那么點集P1到P2的任意兩點的距離都需要我們去驗證是否為最近點對。

對P1'的每一個點, 將它投影到x=mid平面,都可以對它建立一個d*2d*2d的長方體, 所有可選方案都將包含在長方體中, 如圖5所示。

圖5 以映射點展開的d * 2d * 2d 的長方體

可以通過鴿巢原理證明, 最多不超過24個點存在于這個長方體中。那么我們先對P1'和P2'的點進行y為第一關鍵字,z為第二關鍵字的排序。由于點集的y值具有上升的特點，可以通過雙指針的方法維護一個滿足條件的y坐標區間，在常數時間內完成檢測[16]。

（2）算法實現

基于上文的分析，我們可以給出求解三維最近點對的O(nlogn)算法流程圖如圖6所示。

圖6 O(nlogn)算法流程圖

（3） 復雜度證明

如果一個小長方體里面有兩個點，它們最遠的距離是對角線的距離

這與d是最近點對距離的事實矛盾, 因此大長方體里最多24個點。

根據我們的分析, 算法耗費時間T(n)滿足遞歸方程

與我們上文分析的分治法求解二維最近點對問題相似，它的總體時間復雜度級別是O(nlogn)。

3 性能測試

通過在隨機生成的數據下考查算法的時間效率，并采用的在線判題系統的評測機作為速度評判標準，測試結果如表1所示。

表1 測試結果

我們可以對上述結果進行擬合，畫出圖像進行預測，如圖7所示。

圖7 擬合圖像

在實際的測試中，我們的算法實際表現的時間復雜度與理論分析差別不大，分別屬于O（nlogn）和O（n(logn)2）級別。

4 結論

本論文通過對二維最近點對問題的分析，引入了三維空間下的最近點對問題，推廣并提出了兩種利用分治法求三維最近點對問題的高效算法。在現今大數據和高性能計算領域里，對算法的時間復雜度提出了更高的要求，論文中提出的優化在實際計算中能夠大大提升解決問題的效率。