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

《平面點的曼哈頓最小生成樹》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、平面點的曼哈頓最小生成樹引言作者閱讀并研究了由HaiZhou(ElectricalandComputerEngineering,NorthwesternUniversity,Evanston,IL60208,USA)，NarendraShenoy和WilliamNicholls(AdvancedTechnologyGroup,Synopsys,Inc.,MountainView,CA94043,USA)撰寫的論文《EfficientminimumspanningtreeconstructionwithoutDelaunaytriangulat

2、ion》，現(xiàn)將一些收獲體會總結(jié)如下。?問題描述平面上有n個不重合的點，你的任務是求這些點的最小生成樹。兩個點(x0,y0)和(x1,y1)之間的距離定義為

3、x0-x1

4、+

5、y0-y1

6、。（即曼哈頓距離）如果在任意兩個點之間都連一條邊，邊的權(quán)值等于兩點的曼哈頓距離，那么這個題目就是標準的最小生成樹問題。一個包含n個點n2條邊的圖，求最小生成樹的代價是O(n2)。但是這種一般性的做法沒有考慮到“平面”的性質(zhì)。下面將通過分析最小生成樹的性質(zhì)和平面性質(zhì)的結(jié)合，得到一個O(nlogn)的算法。?最小生成樹的“環(huán)切”性質(zhì)先拋開“平面”，我們考慮一般的離散

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

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

9、樹）。證畢。?區(qū)域分類法通過最小生成樹的“環(huán)切”性質(zhì)，我們可以發(fā)現(xiàn)有很多邊是沒有用的。如果圖中存在一個環(huán)，那么就至少能刪掉一條邊而保持最小生成樹不變。我們回到“平面”問題?；舅悸愤€是構(gòu)建一個離散圖——但是這個圖的邊數(shù)必須遠遠小于n2。換句話說我們要想辦法利用“環(huán)切”性質(zhì)，只保留一些有用的邊。考察某個點s。我們從s發(fā)出8條射線將平面均分成八個部分：如果點落在射線上，按如下方法劃分：實線上的點屬于這個區(qū)域、虛線上的點不屬于。上圖中p,q都屬于該區(qū)域。下面我們證明：在每個區(qū)域里面，s只要和至多一個點連邊即可。八個扇形區(qū)域是對稱的，我們只考慮R1。

10、把s看作原點，R1里面的點(x,y)都滿足：x≥0,y>x.考察R1里面兩個點p和q，不失一般性設(shè)xp≤xq。1.??????yp≤yq

11、PQ

12、=xq+yq-(xp+xq)

13、SP

14、=xp+yp

15、SQ

16、=xq+yq所以

17、PQ

18、=

19、SQ

20、-

21、SP

22、≤

23、SQ

24、可見當yp≤yq時，

25、PQ

26、不是三角形SPQ的最長邊。（在曼哈頓距離下的“最長”）2.??????yp>yq0≤xp≤xq≤yq

27、PQ

28、=xq-xp+yp-yq

29、SP

30、=xp+yp

31、SQ

32、=xq+yq即

33、PQ

34、=(yp-xp)+(xq-yq)因為xq≤yq，所以

35、PQ

36、≤yp-xp≤y

37、p≤xp+yp=

38、SP

39、也就是說，當yp>yq時，

40、PQ

41、仍然不是三角形SPQ的最長邊。（曼哈頓距離意義下的“最長”）綜上，

42、PQ

43、無論如何也不可能是三角形SPQ的最長邊。即：在環(huán)中，最大邊只可能是

44、SP

45、和

46、SQ

47、。根據(jù)“環(huán)切”性質(zhì)，我們把

48、SP

49、和

50、SQ

51、中的較長邊刪除即可。假設(shè)R1里面有m個頂點：P1,P2,…,Pm，假設(shè)距離s最近的點是Pk，那么只要在S和Pk之間連邊即可。所謂距離s最近的點，實際上就是xk+yk最小的點。?圖的構(gòu)建方法按照上一節(jié)介紹的方法，我們可以構(gòu)建出一個至多含有8n條邊的圖?？墒侨绾螛?gòu)造呢？如果對于

52、每個點s，把所有的點都判斷一次取最小值，那么復雜度是O(n2)，沒有任何意義。下面我們考慮設(shè)計一個高效的算法，實現(xiàn)“找到每個點的R1區(qū)域內(nèi)，離其最近的點”的操作。找