1、平面點的曼哈頓最小生成樹 引言作者閱讀并研究了由Hai Zhou (Electrical and ComputerEngineering, Northwestern University, Evanston, IL 60208,USA) , Narendra Shenoy和W illiam Nicholls (AdvancedTechnology Group, Sy nopsys, Inc., Mountain View, CA 94043,USA)撰 寫的論文 Efficient minimum spanning tree construction without Delaunay tria

2、ngulation ,現將 一些收獲體會總結如下。問題描述平面上有n個不重合的點，你的任務是求這些點的 最小生成樹。兩個點(x,y。)和(X1,yI)之間的距離定義 為|x0-x1|+|y y|。(即曼哈頓距離)如果在任意兩個點之間都連一條邊，邊的權值等于 兩點的曼哈頓距離，那么這個題目就是標準的最小生 成樹問題。一個包含n個點n2條邊的圖，求最小生成 樹的代價是O(n2)。但是這種一般性的做法沒有考慮到 “平面”的性質。下面將通過分析最小生成樹的性質 和平面性質的結合，得到一個O(nlogn)的算法。最小生成樹的“環切”性質先拋開“平面”，我們考慮一般的離散圖的最小生 成樹有什么性質。環切性

3、質 在圖 G=(V,E)G=(V,E)中，如果存在一個環，把環 中權最大的邊 e e 刪除得到圖 G G =(V,Ee)=(V,Ee)(如果有 多條最大邊，則刪除任意一條)，則 G G 和GJ的最小 生成樹權和相同。證明：假設e(e E)在G的一個環C上，并且是環上的權最大邊。假設G的某棵最小生成樹T包含了e,考慮e連接 的兩個點u和v。把e從T中刪除，就把T分成兩個 連通分量，u,v分處不同的連通分量。在環C上對應 的把e刪除，從u到v還是有一條通路，并且通路上 的所有邊權值都不大于e的權值；假設這條通路是(u, X1, x2, , xL, v)。在點集S=u, X1, X2, , XL,

4、v中，和u屬于同 一個集合的點稱之為紅點， 和v屬于同一個集合的稱 之為藍點。顯然S中至少有一個紅點(u)、至少有一個 藍點(v)。所以在序列(u, X1, X2, , XL, v)中必然 存在相鄰的兩個點顏色不同，不妨設為a和b。將入到被刪除了e的T中，就得到了一棵新的生成樹T ：即T =(T(e) U (。前面提到了通路(u,xi, x2, , xL,v)中任意一條邊都不大于e,所以的權不大于e的權。即T也是G的一棵最小生 成樹。因為G?是G的子圖，所以T也是G的最小生成 樹。而T和T的權和相等(都是G的最小生成樹)。證畢。區域分類法通過最小生成樹的“環切”性質，我們可以發現有 很多邊是沒

5、有用的。如果圖中存在一個環，那么就至 少能刪掉一條邊而保持最小生成樹不變。我們回到“平面”問題。基本思路還是構建一個離散圖一一但是這個圖的邊數必須遠遠小于n2。換句話說我們要想辦法利用“環切”性質，只保留一些有用 的邊。考察某個點s。我們從s發出8條射線將平面均分 成八個部分：XX/ RsR4如果點落在射線上，按如下方法劃分:p,/I1szz z/F實線上的點屬于這個區域、虛線上的點不屬于。上 圖中p, q都屬于該區域。下面我們證明：在每個區域里面，s只要和至多一 個點連邊即可。八個扇形區域是對稱的，我們只考慮R。把s看作原點，R里面的點(x,y)都滿足：x 0,yx.考察R里面兩個點p和q,

6、不失一般性設xp xq。1. ypVyq|PQ|=xq+yq-(xp+xq)|SP|=xp+yp|SQ|=Xq+yq所以|PQ|=|SQ|- |SP| yq0X p XqV y qyq時，|PQ|仍然不是三角形SPQ的最長邊。(曼哈頓距離意義下的最長)綜上，|PQ|無論如何也不可能是三角形SPQ勺最長 邊。即：在環中，最大邊只可能是|SP|和| SQ|。根據“環切”性質，我們把|SP|和|SQ|中的較長 邊刪除即可。假設R里面有m個頂點：Pl, P2, , Pm,假設距離s最近的點是R,那么只要在S和R之間連邊即可。所謂距離s最近的點，實際上就是xk+yk最小的點。圖的構建方法按照上一節介紹的

7、方法，我們可以構建出一個至多 含有8n條邊的圖。可是如何構造呢？如果對于每個點s,把所有的點都判斷一次取最小值，那么復雜度是O(n2),沒有任何意義。下面我們考慮設計一個高效的 算法，實現“找到每個點的R區域內，離其最近的點” 的操作。找s的R區域內離s最近的點，實際上就是找s的R區域內x+y最小的點。我們把所有的點按照x從小到大排序：xix2 ,Xk2.y-xyk-xk要滿足第一個條件，Q必須屬于集合Pk+1, Pk+2, Pn,即Q必然在T中。要滿足第二個條件，Q在T中的第一關鍵字必須大 于yk-xk(定值)。因為我們要使得|PkQ|最小，所以我們實際上就是：從T的第一關鍵字大于某常數的所

8、有元素中，尋找第 二關鍵字最小的元素。很明顯，T可以用平衡二叉樹來實現。按照第一關 鍵字有序來建立平衡樹，對于平衡樹每個節點都記錄 以其為根的子樹中第二關鍵字最小的是哪個元素。查 詢、插入的時間復雜度都是O(logn)。平衡二叉樹也可以用線段樹代替。對于R,找到符合上述條件并使|PkQ|最小的Q之后, 在Pk和Q之間連一條邊，并將R插入T;繼續處理Pk-1(除非k=1)。經過上面的處理，我們就把每個點在R區域內的最 近點求出來了。同樣的處理R, R3, , R8即可把整 個離散圖構建出來。一點優化如果把R, R2, , R8分別處理，則整個算法的復雜度系數過大XX/芯R4我們很容易注意到，R和

9、R是對稱的，只要處理其 中一個區域即可。根據對稱性，我們只要處理R, R2, R3, R4這四個區域。如果點(x,y)在Ps的R區域內，貝U:1.XXk2.y-xyk-xk如果點(x,y)在Ps的R區域內，貝U:1.xXk2.y-x”和” ”的區別。處理R的時候，任意時刻處理R,我們希望找T中 第一關鍵字大于某常數的第二關鍵字最小元素； 處理R的時候，任意時刻處理R,我們要找的就是T中第 一關鍵字小于某常數的第二關鍵字最小元素。因而很容易發現,R和R可以和在一起處理。這樣我們只要處理R+R、R+R這兩種情況即可。時 間復雜度的常系數從8降低到了2。我們按照這樣的方法建立的離散圖至多含有8n條 邊。對該圖求最小生成樹的時間復雜度為O(