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

《平面點的曼哈頓最小生成樹》由會員上傳分享，免費在線閱讀，更多相關內容在應用文檔-天天文庫。

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

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

3、x0-x1

4、+

5、y0-y1

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

7、?最小生成樹的“環(huán)切”性質先拋開“平面”，我們考慮一般的離散圖的最小生成樹有什么性質。環(huán)切性質在圖G=(V,E)中，如果存在一個環(huán)，把環(huán)中權最大的邊e刪除得到圖G’=(V,E{e})（如果有多條最大邊，則刪除任意一條），則G和G’的最小生成樹權和相同。證明：假設e(e∈E)在G的一個環(huán)C上，并且是環(huán)上的權最大邊。假設G的某棵最小生成樹T包含了e，考慮e連接的兩個點u和v。把e從T中刪除，就把T分成兩個連通分量，u,v分處不同的連通分量。在環(huán)C上對應的把e刪除，從u到v還是有一條通路，并且通路上的所有邊權值都不大

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

9、。即T’也是G的一棵最小生成樹。因為G’是G的子圖，所以T’也是G’的最小生成樹。而T和T’的權和相等（都是G的最小生成樹）。證畢。?區(qū)域分類法通過最小生成樹的“環(huán)切”性質，我們可以發(fā)現(xiàn)有很多邊是沒有用的。如果圖中存在一個環(huán)，那么就至少能刪掉一條邊而保持最小生成樹不變。我們回到“平面”問題。基本思路還是構建一個離散圖——但是這個圖的邊數(shù)必須遠遠小于n2。換句話說我們要想辦法利用“環(huán)切”性質，只保留一些有用的邊。考察某個點s。我們從s發(fā)出8條射線將平面均分成八個部分：如果點落在射線上，按如下方法劃分：實線上的點屬于

10、這個區(qū)域、虛線上的點不屬于。上圖中p,q都屬于該區(qū)域。下面我們證明：在每個區(qū)域里面，s只要和至多一個點連邊即可。八個扇形區(qū)域是對稱的，我們只考慮R1。把s看作原點，R1里面的點(x,y)都滿足：x≥0,y>x.考察R1里面兩個點p和q，不失一般性設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≤

27、xp≤xq≤yq

28、PQ

29、=xq-xp+yp-yq

30、SP

31、=xp+yp

32、SQ

33、=xq+yq即

34、PQ

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

36、PQ

37、≤yp-xp≤yp≤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)切”性質，我們把

48、SP

49、和

50、SQ

51、中的較長邊刪除即可。假設R1里面有m個頂點：P1,P2,…,Pm

52、，假設距離s最近的點是Pk，那么只要在S和Pk之間連邊即可。所謂距離s最近的點，實際上就是xk+yk最小的點。?圖的構建方法按照上一節(jié)介紹的方法，我們可以構建出一個至多含有8n條邊的圖?？墒侨绾螛嬙炷?？如果對于每個點s，把所有的點都判斷一次取最小值，那么復雜度是O(n2)，沒有任何意義。下面我們考慮設計一個高效的算法，實現(xiàn)“找到每個點的R1區(qū)域內，離其最近的點”的操作。找