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

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

4、點(diǎn)。顯然S中至少有一個(gè)紅點(diǎn)(u)、至少有一個(gè)藍(lán)點(diǎn)(v)。所以在序列(u, x1, x2, , xL, v)中必然存在相鄰的兩個(gè)點(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、存在一個(gè)環(huán)，那么就至少能刪掉一條邊而保持最小生成樹不變。我們回到“平面”問題。基本思路還是構(gòu)建一個(gè)離散圖但是這個(gè)圖的邊數(shù)必須遠(yuǎn)遠(yuǎn)小于n2。換句話說我們要想辦法利用“環(huán)切”性質(zhì)，只保留一些有用的邊?？疾炷硞€(gè)點(diǎn)s。我們從s發(fā)出8條射線將平面均分成八個(gè)部分：如果點(diǎn)落在射線上，按如下方法劃分：實(shí)線上的點(diǎn)屬于這個(gè)區(qū)域、虛線上的點(diǎn)不屬于。上圖中p, q都屬于該區(qū)域。下面我們證明：在每個(gè)區(qū)域里面，s只要和至多一個(gè)點(diǎn)連邊即可。八個(gè)扇形區(qū)域是對(duì)稱的，我們只考慮R1。把s看作原點(diǎn)，R1里面的點(diǎn)(x,y)都滿足：x0,y>x.考察R1里面兩個(gè)點(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時(shí)，|PQ|不是三角形SPQ的最長(zhǎng)邊。（在曼哈頓距離下的“最長(zhǎng)”）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時(shí)，|PQ|仍然不是三角形SPQ

7、的最長(zhǎng)邊。（曼哈頓距離意義下的“最長(zhǎng)”）綜上，|PQ|無論如何也不可能是三角形SPQ的最長(zhǎng)邊。即：在環(huán)<s, p, q>中，最大邊只可能是|SP|和|SQ|。根據(jù)“環(huán)切”性質(zhì)，我們把|SP|和|SQ|中的較長(zhǎng)邊刪除即可。假設(shè)R1里面有m個(gè)頂點(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)建出一個(gè)至多含有8n條邊的圖?？墒侨绾螛?gòu)造呢？如果對(duì)于每個(gè)點(diǎn)s，把所有的點(diǎn)都判斷一次取最小值，那么復(fù)雜度是O(n2)，沒有任何意義。下面我們考慮設(shè)計(jì)一個(gè)高

8、效的算法，實(shí)現(xiàn)“找到每個(gè)點(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。建立一個(gè)抽象數(shù)據(jù)結(jié)構(gòu)T。T中的每個(gè)元素對(duì)應(yīng)平面上的一個(gè)點(diǎn)(x,y)，該元素的第一關(guān)鍵字等于y-x，第二關(guān)鍵字等于y+x。從Pn到P1逐個(gè)處理每個(gè)點(diǎn)。處理Pk的時(shí)候，令Pk+1, Pk+2, , Pn都已經(jīng)存入到T中。某個(gè)點(diǎn)Q(x,y)如果落在Pk的R1區(qū)間內(nèi)，必須滿足：1.       xxk2.     

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

10、；繼續(xù)處理Pk-1(除非k=1)。經(jīng)過上面的處理，我們就把每個(gè)點(diǎn)在R1區(qū)域內(nèi)的最近點(diǎn)求出來了。同樣的處理R2, R3, , R8即可把整個(gè)離散圖構(gòu)建出來。 一點(diǎn)優(yōu)化如果把R1, R2, , R8分別處理，則整個(gè)算法的復(fù)雜度系數(shù)過大。我們很容易注意到，R1和R5是對(duì)稱的，只要處理其中一個(gè)區(qū)域即可。根據(jù)對(duì)稱性，我們只要處理R1, R2, R3, R4這四個(gè)區(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以上兩組條件僅是一個(gè)”>”和”<”的區(qū)別。處理R1的時(shí)候，任意時(shí)刻處理Pk，我們希望找T中第一關(guān)鍵字大于某常數(shù)的第二關(guān)鍵字最小元素；處理R2的時(shí)候，任意時(shí)刻處理Pk，我們要找的就是T中第一關(guān)鍵字小于某常數(shù)的第二關(guān)鍵字最小元素。因而很容易發(fā)現(xiàn)，R1和R2可以和在一起處理。這樣我們只要處理R1+R2、R3+R4這兩種情況即可。時(shí)間復(fù)雜度的常系數(shù)從8降低到了2。我們按照這樣的方法建立的離散圖至多