平面點的曼哈頓最小生成樹

引言

作者閱讀并研究了由Hai Zhou (Electrical and Computer Engineering, Northwestern University, Evanston, IL 60208, USA)，Narendra Shenoy和William Nicholls (Advanced Technology Group, Synopsys, Inc., Mountain View, CA 94043, USA)撰寫的論文《Efficient minimum spanning tree construction without Delaunay triangulation》，現將一些收獲體會總結如下。

問題描述

平面上有n個不重合的點，你的任務是求這些點的最小生成樹。兩個點(x₀,y₀)和(x₁,y₁)之間的距離定義為|x₀-x₁|+|y₀-y₁|。（即曼哈頓距離）

如果在任意兩個點之間都連一條邊，邊的權值等于兩點的曼哈頓距離，那么這個題目就是標準的最小生成樹問題。一個包含n個點n²條邊的圖，求最小生成樹的代價是O(n²)。但是這種一般性的做法沒有考慮到“平面”的性質。下面將通過分析最小生成樹的性質和平面性質的結合，得到一個O(nlogn)的算法。

最小生成樹的“環切”性質

先拋開“平面”，我們考慮一般的離散圖的最小生成樹有什么性質。

環切性質 在圖G=(V,E)中，如果存在一個環，把環中權最大的邊e刪除得到圖G’=(V,E\{e})（如果有多條最大邊，則刪除任意一條），則G和G’的最小生成樹權和相同。

證明：

假設e(e∈E)在G的一個環C上，并且是環上的權最大邊。

假設G的某棵最小生成樹T包含了e，考慮e連接的兩個點u和v。把e從T中刪除，就把T分成兩個連通分量，u,v分處不同的連通分量。在環C上對應的把e刪除，從u到v還是有一條通路，并且通路上的所有邊權值都不大于e的權值；假設這條通路是(u, x₁, x₂, …, x_L, v)。

在點集S={u, x₁, x₂, …, x_L, v}中，和u屬于同一個集合的點稱之為紅點，和v屬于同一個集合的稱之為藍點。顯然S中至少有一個紅點(u)、至少有一個藍點(v)。所以在序列(u, x₁, x₂, …, x_L, v)中必然存在相鄰的兩個點顏色不同，不妨設為a和b。將<a,b>加入到被刪除了e的T中，就得到了一棵新的生成樹T’：即T’=(T\{e})∪{<a,b>}。前面提到了通路(u, x₁, x₂, …, x_L, v)中任意一條邊都不大于e，所以<a,b>的權不大于e的權。即T’也是G的一棵最小生成樹。

因為G’是G的子圖，所以T’也是G’的最小生成樹。而T和T’的權和相等（都是G的最小生成樹）。

證畢。

區域分類法

通過最小生成樹的“環切”性質，我們可以發現有很多邊是沒有用的。如果圖中存在一個環，那么就至少能刪掉一條邊而保持最小生成樹不變。

我們回到“平面”問題。基本思路還是構建一個離散圖——但是這個圖的邊數必須遠遠小于n²。換句話說我們要想辦法利用“環切”性質，只保留一些有用的邊。

考察某個點s。我們從s發出8條射線將平面均分成八個部分：

如果點落在射線上，按如下方法劃分：

實線上的點屬于這個區域、虛線上的點不屬于。上圖中p, q都屬于該區域。

下面我們證明：在每個區域里面，s只要和至多一個點連邊即可。

八個扇形區域是對稱的，我們只考慮R₁。

把s看作原點，R₁里面的點(x,y)都滿足：

x≥0,

y>x.

考察R₁里面兩個點p和q，不失一般性設x_p≤x_q。

1.       y_p≤y_q

|PQ|=x_q+y_q-(x_p+x_q)

|SP|=x_p+y_p

|SQ|=x_q+y_q

所以|PQ|=|SQ|-|SP|≤|SQ|

可見當y_p≤y_q時，|PQ|不是三角形SPQ的最長邊。（在曼哈頓距離下的“最長”）

2.       y_p>y_q­

0≤x_p≤x_q≤y_q<y_p

|PQ|=x_q-x_p+y_p-y_q

|SP|=x_p+y_p

|SQ|=x_q+y_q

即|PQ|= (y_p-x_p)+(x_q-y_q)

因為x_q≤y_q，所以|PQ|≤yp-xp≤yp≤xp+yp=|SP|

也就是說，當y_p>y_q時，|PQ|仍然不是三角形SPQ的最長邊。（曼哈頓距離意義下的“最長”）

綜上，|PQ|無論如何也不可能是三角形SPQ的最長邊。即：在環<s, p, q>中，最大邊只可能是|SP|和|SQ|。根據“環切”性質，我們把|SP|和|SQ|中的較長邊刪除即可。

假設R₁里面有m個頂點：P₁, P₂, …, P_m，假設距離s最近的點是P_k，那么只要在S和P_k之間連邊即可。

所謂距離s最近的點，實際上就是x_k+y_k最小的點。

圖的構建方法

按照上一節介紹的方法，我們可以構建出一個至多含有8n條邊的圖。可是如何構造呢？如果對于每個點s，把所有的點都判斷一次取最小值，那么復雜度是O(n²)，沒有任何意義。下面我們考慮設計一個高效的算法，實現“找到每個點的R₁區域內，離其最近的點”的操作。

找s的R₁區域內離s最近的點，實際上就是找s的R₁區域內x+y最小的點。

我們把所有的點按照x從小到大排序：x₁≤x₂≤…≤x_n。

建立一個抽象數據結構T。T中的每個元素對應平面上的一個點(x,y)，該元素的第一關鍵字等于y-x，第二關鍵字等于y+x。

從P_n到P₁逐個處理每個點。處理Pk的時候，令P_k+1, P_k+2, …, P_n都已經存入到T中。某個點Q(x,y)如果落在P_k的R₁區間內，必須滿足：

1.       x≥x_k

2.       y-x>y_k-x_k

要滿足第一個條件，Q必須屬于集合{P_k+1, P_k+2, …, P_n}，即Q必然在T中。

要滿足第二個條件，Q在T中的第一關鍵字必須大于y_k-x_k(定值)。

因為我們要使得|P_kQ|最小，所以我們實際上就是：從T的第一關鍵字大于某常數的所有元素中，尋找第二關鍵字最小的元素。

很明顯，T可以用平衡二叉樹來實現。按照第一關鍵字有序來建立平衡樹，對于平衡樹每個節點都記錄以其為根的子樹中第二關鍵字最小的是哪個元素。查詢、插入的時間復雜度都是O(logn)。

平衡二叉樹也可以用線段樹代替。

對于P_k，找到符合上述條件并使|P_kQ|最小的Q之后，在P_k和Q之間連一條邊，并將P_k插入T；繼續處理P_k-1(除非k=1)。

經過上面的處理，我們就把每個點在R₁區域內的最近點求出來了。同樣的處理R₂, R₃, …, R₈即可把整個離散圖構建出來。

一點優化

如果把R₁, R₂, …, R₈分別處理，則整個算法的復雜度系數過大。

我們很容易注意到，R₁和R₅是對稱的，只要處理其中一個區域即可。根據對稱性，我們只要處理R₁, R₂, R₃, R₄這四個區域。

如果點(x,y)在P_s的R₁區域內，則：

1.       x≥x_k

2.       y-x>y_k-x_k

如果點(x,y)在P_s的R₂區域內，則：

1.       x≥x_k

2.       y-x<y_k-x_k

以上兩組條件僅是一個”>”和”<”的區別。

處理R₁的時候，任意時刻處理P_k，我們希望找T中第一關鍵字大于某常數的第二關鍵字最小元素；處理R₂的時候，任意時刻處理P_k，我們要找的就是T中第一關鍵字小于某常數的第二關鍵字最小元素。

因而很容易發現，R₁和R₂可以和在一起處理。

這樣我們只要處理R₁+R₂、R₃+R₄這兩種情況即可。時間復雜度的常系數從8降低到了2。

我們按照這樣的方法建立的離散圖至多含有8n條邊。對該圖求最小生成樹的時間復雜度為O(nlogn)；之前建圖的復雜度也是O(nlogn)，所以總時間復雜度O(nlogn)。空間復雜度O(n)。

總結

這個題目最值得稱道的地方就是“分區域”。“分區域”充分利用了平面性質，結合一般情況下最小生成樹都具有的環切性質，該方法取得了奇效。

我們研究問題的時候也應該注意充分利用已有信息。