平面點(diǎn)的曼哈頓最小生成樹

1、平面點(diǎn)的曼哈頓最小生成樹引言作者閱讀并研究了由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 triangu

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

3、切性質(zhì) 在圖G=(V,E)中，如果存在一個環(huán)，把環(huán)中權(quán)最大的邊e刪除得到圖G=(V,Ee)（如果有多條最大邊，則刪除任意一條），則G和G的最小生成樹權(quán)和相同。證明：假設(shè)e(eE)在G的一個環(huán)C上，并且是環(huán)上的權(quán)最大邊。假設(shè)G的某棵最小生成樹T包含了e，考慮e連接的兩個點(diǎn)u和v。把e從T中刪除，就把T分成兩個連通分量，u,v分處不同的連通分量。在環(huán)C上對應(yīng)的把e刪除，從u到v還是有一條通路，并且通路上的所有邊權(quán)值都不大于e的權(quán)值；假設(shè)這條通路是(u, x1, x2, , xL, v)。在點(diǎn)集S=u, x1, x2, , xL, v中，和u屬于同一個集合的點(diǎn)稱之為紅點(diǎn)，和v屬于同一個集合的稱之為藍(lán)

4、點(diǎn)。顯然S中至少有一個紅點(diǎn)(u)、至少有一個藍(lán)點(diǎn)(v)。所以在序列(u, x1, x2, , xL, v)中必然存在相鄰的兩個點(diǎn)顏色不同，不妨設(shè)為a和b。將<a,b>加入到被刪除了e的T中，就得到了一棵新的生成樹T：即T=(Te)<a,b>。前面提到了通路(u, x1, x2, , xL, v)中任意一條邊都不大于e，所以<a,b>的權(quán)不大于e的權(quán)。即T也是G的一棵最小生成樹。因?yàn)镚是G的子圖，所以T也是G的最小生成樹。而T和T的權(quán)和相等（都是G的最小生成樹）。證畢。 區(qū)域分類法通過最小生成樹的“環(huán)切”性質(zhì)，我們可以發(fā)現(xiàn)有很多邊是沒有用的。如果圖中

5、存在一個環(huán)，那么就至少能刪掉一條邊而保持最小生成樹不變。我們回到“平面”問題?；舅悸愤€是構(gòu)建一個離散圖但是這個圖的邊數(shù)必須遠(yuǎn)遠(yuǎn)小于n2。換句話說我們要想辦法利用“環(huán)切”性質(zhì)，只保留一些有用的邊?？疾炷硞€點(diǎn)s。我們從s發(fā)出8條射線將平面均分成八個部分：如果點(diǎn)落在射線上，按如下方法劃分：實(shí)線上的點(diǎn)屬于這個區(qū)域、虛線上的點(diǎn)不屬于。上圖中p, q都屬于該區(qū)域。下面我們證明：在每個區(qū)域里面，s只要和至多一個點(diǎn)連邊即可。八個扇形區(qū)域是對稱的，我們只考慮R1。把s看作原點(diǎn)，R1里面的點(diǎn)(x,y)都滿足：x0,y>x.考察R1里面兩個點(diǎn)p和q，不失一般性設(shè)xpxq。1.  

6、0;    ypyq|PQ|=xq+yq-(xp+xq)|SP|=xp+yp|SQ|=xq+yq所以|PQ|=|SQ|-|SP|SQ|可見當(dāng)ypyq時，|PQ|不是三角形SPQ的最長邊。（在曼哈頓距離下的“最長”）2.       yp>yq0xpxqyq<yp|PQ|=xq-xp+yp-yq|SP|=xp+yp|SQ|=xq+yq即|PQ|= (yp-xp)+(xq-yq)因?yàn)閤qyq，所以|PQ|yp-xpypxp+yp=|SP|也就是說，當(dāng)yp>yq時，|PQ|仍然不是三角形SPQ

7、的最長邊。（曼哈頓距離意義下的“最長”）綜上，|PQ|無論如何也不可能是三角形SPQ的最長邊。即：在環(huán)<s, p, q>中，最大邊只可能是|SP|和|SQ|。根據(jù)“環(huán)切”性質(zhì)，我們把|SP|和|SQ|中的較長邊刪除即可。假設(shè)R1里面有m個頂點(diǎn)：P1, P2, , Pm，假設(shè)距離s最近的點(diǎn)是Pk，那么只要在S和Pk之間連邊即可。所謂距離s最近的點(diǎn)，實(shí)際上就是xk+yk最小的點(diǎn)。 圖的構(gòu)建方法按照上一節(jié)介紹的方法，我們可以構(gòu)建出一個至多含有8n條邊的圖?？墒侨绾螛?gòu)造呢？如果對于每個點(diǎn)s，把所有的點(diǎn)都判斷一次取最小值，那么復(fù)雜度是O(n2)，沒有任何意義。下面我們考慮設(shè)計一個高

8、效的算法，實(shí)現(xiàn)“找到每個點(diǎn)的R1區(qū)域內(nèi)，離其最近的點(diǎn)”的操作。找s的R1區(qū)域內(nèi)離s最近的點(diǎn)，實(shí)際上就是找s的R1區(qū)域內(nèi)x+y最小的點(diǎn)。我們把所有的點(diǎn)按照x從小到大排序：x1x2xn。建立一個抽象數(shù)據(jù)結(jié)構(gòu)T。T中的每個元素對應(yīng)平面上的一個點(diǎn)(x,y)，該元素的第一關(guān)鍵字等于y-x，第二關(guān)鍵字等于y+x。從Pn到P1逐個處理每個點(diǎn)。處理Pk的時候，令Pk+1, Pk+2, , Pn都已經(jīng)存入到T中。某個點(diǎn)Q(x,y)如果落在Pk的R1區(qū)間內(nèi)，必須滿足：1.       xxk2.     

9、  y-x>yk-xk要滿足第一個條件，Q必須屬于集合Pk+1, Pk+2, , Pn，即Q必然在T中。要滿足第二個條件，Q在T中的第一關(guān)鍵字必須大于yk-xk(定值)。因?yàn)槲覀円沟脇PkQ|最小，所以我們實(shí)際上就是：從T的第一關(guān)鍵字大于某常數(shù)的所有元素中，尋找第二關(guān)鍵字最小的元素。很明顯，T可以用平衡二叉樹來實(shí)現(xiàn)。按照第一關(guān)鍵字有序來建立平衡樹，對于平衡樹每個節(jié)點(diǎn)都記錄以其為根的子樹中第二關(guān)鍵字最小的是哪個元素。查詢、插入的時間復(fù)雜度都是O(logn)。平衡二叉樹也可以用線段樹代替。對于Pk，找到符合上述條件并使|PkQ|最小的Q之后，在Pk和Q之間連一條邊，并將Pk插入T

10、；繼續(xù)處理Pk-1(除非k=1)。經(jīng)過上面的處理，我們就把每個點(diǎn)在R1區(qū)域內(nèi)的最近點(diǎn)求出來了。同樣的處理R2, R3, , R8即可把整個離散圖構(gòu)建出來。 一點(diǎn)優(yōu)化如果把R1, R2, , R8分別處理，則整個算法的復(fù)雜度系數(shù)過大。我們很容易注意到，R1和R5是對稱的，只要處理其中一個區(qū)域即可。根據(jù)對稱性，我們只要處理R1, R2, R3, R4這四個區(qū)域。如果點(diǎn)(x,y)在Ps的R1區(qū)域內(nèi)，則：1.       xxk2.       y-x>yk-xk如果

11、點(diǎn)(x,y)在Ps的R2區(qū)域內(nèi)，則：1.       xxk2.       y-x<yk-xk以上兩組條件僅是一個”>”和”<”的區(qū)別。處理R1的時候，任意時刻處理Pk，我們希望找T中第一關(guān)鍵字大于某常數(shù)的第二關(guān)鍵字最小元素；處理R2的時候，任意時刻處理Pk，我們要找的就是T中第一關(guān)鍵字小于某常數(shù)的第二關(guān)鍵字最小元素。因而很容易發(fā)現(xiàn)，R1和R2可以和在一起處理。這樣我們只要處理R1+R2、R3+R4這兩種情況即可。時間復(fù)雜度的常系數(shù)從8降低到了2。我們按照這樣的方法建立的離散圖至多