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

引言

作者閱讀并研究了由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)撰寫(xiě)的論文《Efficient minimum spanning tree construction without Delaunay triangulation》，現(xiàn)將一些收獲體會(huì)總結(jié)如下。

問(wèn)題描述

平面上有n個(gè)不重合的點(diǎn)，你的任務(wù)是求這些點(diǎn)的最小生成樹(shù)。兩個(gè)點(diǎn)(x₀,y₀)和(x₁,y₁)之間的距離定義為|x₀-x₁|+|y₀-y₁|。（即曼哈頓距離）

如果在任意兩個(gè)點(diǎn)之間都連一條邊，邊的權(quán)值等于兩點(diǎn)的曼哈頓距離，那么這個(gè)題目就是標(biāo)準(zhǔn)的最小生成樹(shù)問(wèn)題。一個(gè)包含n個(gè)點(diǎn)n²條邊的圖，求最小生成樹(shù)的代價(jià)是O(n²)。但是這種一般性的做法沒(méi)有考慮到“平面”的性質(zhì)。下面將通過(guò)分析最小生成樹(shù)的性質(zhì)和平面性質(zhì)的結(jié)合，得到一個(gè)O(nlogn)的算法。

最小生成樹(shù)的“環(huán)切”性質(zhì)

先拋開(kāi)“平面”，我們考慮一般的離散圖的最小生成樹(shù)有什么性質(zhì)。

環(huán)切性質(zhì) 在圖G=(V,E)中，如果存在一個(gè)環(huán)，把環(huán)中權(quán)最大的邊e刪除得到圖G’=(V,E\{e})（如果有多條最大邊，則刪除任意一條），則G和G’的最小生成樹(shù)權(quán)和相同。

證明：

假設(shè)e(e∈E)在G的一個(gè)環(huán)C上，并且是環(huán)上的權(quán)最大邊。

假設(shè)G的某棵最小生成樹(shù)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, x₁, x₂, …, x_L, v)。

在點(diǎn)集S={u, x₁, x₂, …, x_L, v}中，和u屬于同一個(gè)集合的點(diǎn)稱(chēng)之為紅點(diǎn)，和v屬于同一個(gè)集合的稱(chēng)之為藍(lán)點(diǎn)。顯然S中至少有一個(gè)紅點(diǎn)(u)、至少有一個(gè)藍(lán)點(diǎn)(v)。所以在序列(u, x₁, x₂, …, x_L, v)中必然存在相鄰的兩個(gè)點(diǎn)顏色不同，不妨設(shè)為a和b。將<a,b>加入到被刪除了e的T中，就得到了一棵新的生成樹(shù)T’：即T’=(T\{e})∪{<a,b>}。前面提到了通路(u, x₁, x₂, …, x_L, v)中任意一條邊都不大于e，所以<a,b>的權(quán)不大于e的權(quán)。即T’也是G的一棵最小生成樹(shù)。

因?yàn)?/span>G’是G的子圖，所以T’也是G’的最小生成樹(shù)。而T和T’的權(quán)和相等（都是G的最小生成樹(shù)）。

證畢。

區(qū)域分類(lèi)法

通過(guò)最小生成樹(shù)的“環(huán)切”性質(zhì)，我們可以發(fā)現(xiàn)有很多邊是沒(méi)有用的。如果圖中存在一個(gè)環(huán)，那么就至少能刪掉一條邊而保持最小生成樹(shù)不變。

我們回到“平面”問(wèn)題。基本思路還是構(gòu)建一個(gè)離散圖——但是這個(gè)圖的邊數(shù)必須遠(yuǎn)遠(yuǎn)小于n²。換句話說(shuō)我們要想辦法利用“環(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ì)稱(chēng)的，我們只考慮R₁。

把s看作原點(diǎn)，R₁里面的點(diǎn)(x,y)都滿(mǎn)足：

x≥0,

y>x.

考察R₁里面兩個(gè)點(diǎn)p和q，不失一般性設(shè)x_p≤x_q。

1.       y_p≤y_q

|PQ|=x_q+y_q-(x_p+x_q)

|SP|=x_p+y_p

|SQ|=x_q+y_q

所以|PQ|=|SQ|-|SP|≤|SQ|

可見(jiàn)當(dāng)y_p≤y_q時(shí)，|PQ|不是三角形SPQ的最長(zhǎng)邊。（在曼哈頓距離下的“最長(zhǎng)”）

2.       y_p>y_q­

0≤x_p≤x_q≤y_q<y_p

|PQ|=x_q-x_p+y_p-y_q

|SP|=x_p+y_p

|SQ|=x_q+y_q

即|PQ|= (y_p-x_p)+(x_q-y_q)

因?yàn)?/span>x_q≤y_q，所以|PQ|≤yp-xp≤yp≤xp+yp=|SP|

也就是說(shuō)，當(dāng)y_p>y_q時(shí)，|PQ|仍然不是三角形SPQ的最長(zhǎng)邊。（曼哈頓距離意義下的“最長(zhǎng)”）

綜上，|PQ|無(wú)論如何也不可能是三角形SPQ的最長(zhǎng)邊。即：在環(huán)<s, p, q>中，最大邊只可能是|SP|和|SQ|。根據(jù)“環(huán)切”性質(zhì)，我們把|SP|和|SQ|中的較長(zhǎng)邊刪除即可。

假設(shè)R₁里面有m個(gè)頂點(diǎn)：P₁, P₂, …, P_m，假設(shè)距離s最近的點(diǎn)是P_k，那么只要在S和P_k之間連邊即可。

所謂距離s最近的點(diǎn)，實(shí)際上就是x_k+y_k最小的點(diǎn)。

圖的構(gòu)建方法

按照上一節(jié)介紹的方法，我們可以構(gòu)建出一個(gè)至多含有8n條邊的圖。可是如何構(gòu)造呢？如果對(duì)于每個(gè)點(diǎn)s，把所有的點(diǎn)都判斷一次取最小值，那么復(fù)雜度是O(n²)，沒(méi)有任何意義。下面我們考慮設(shè)計(jì)一個(gè)高效的算法，實(shí)現(xiàn)“找到每個(gè)點(diǎn)的R₁區(qū)域內(nèi)，離其最近的點(diǎn)”的操作。

找s的R₁區(qū)域內(nèi)離s最近的點(diǎn)，實(shí)際上就是找s的R₁區(qū)域內(nèi)x+y最小的點(diǎn)。

我們把所有的點(diǎn)按照x從小到大排序：x₁≤x₂≤…≤x_n。

建立一個(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。

從P_n到P₁逐個(gè)處理每個(gè)點(diǎn)。處理Pk的時(shí)候，令P_k+1, P_k+2, …, P_n都已經(jīng)存入到T中。某個(gè)點(diǎn)Q(x,y)如果落在P_k的R₁區(qū)間內(nèi)，必須滿(mǎn)足：

1.       x≥x_k

2.       y-x>y_k-x_k

要滿(mǎn)足第一個(gè)條件，Q必須屬于集合{P_k+1, P_k+2, …, P_n}，即Q必然在T中。

要滿(mǎn)足第二個(gè)條件，Q在T中的第一關(guān)鍵字必須大于y_k-x_k(定值)。

因?yàn)槲覀円沟?/span>|P_kQ|最小，所以我們實(shí)際上就是：從T的第一關(guān)鍵字大于某常數(shù)的所有元素中，尋找第二關(guān)鍵字最小的元素。

很明顯，T可以用平衡二叉樹(shù)來(lái)實(shí)現(xiàn)。按照第一關(guān)鍵字有序來(lái)建立平衡樹(shù)，對(duì)于平衡樹(shù)每個(gè)節(jié)點(diǎn)都記錄以其為根的子樹(shù)中第二關(guān)鍵字最小的是哪個(gè)元素。查詢(xún)、插入的時(shí)間復(fù)雜度都是O(logn)。

平衡二叉樹(shù)也可以用線段樹(shù)代替。

對(duì)于P_k，找到符合上述條件并使|P_kQ|最小的Q之后，在P_k和Q之間連一條邊，并將P_k插入T；繼續(xù)處理P_k-1(除非k=1)。

經(jīng)過(guò)上面的處理，我們就把每個(gè)點(diǎn)在R₁區(qū)域內(nèi)的最近點(diǎn)求出來(lái)了。同樣的處理R₂, R₃, …, R₈即可把整個(gè)離散圖構(gòu)建出來(lái)。

一點(diǎn)優(yōu)化

如果把R₁, R₂, …, R₈分別處理，則整個(gè)算法的復(fù)雜度系數(shù)過(guò)大。

我們很容易注意到，R₁和R₅是對(duì)稱(chēng)的，只要處理其中一個(gè)區(qū)域即可。根據(jù)對(duì)稱(chēng)性，我們只要處理R₁, R₂, R₃, R₄這四個(gè)區(qū)域。

如果點(diǎn)(x,y)在P_s的R₁區(qū)域內(nèi)，則：

1.       x≥x_k

2.       y-x>y_k-x_k

如果點(diǎn)(x,y)在P_s的R₂區(qū)域內(nèi)，則：

1.       x≥x_k

2.       y-x<y_k-x_k

以上兩組條件僅是一個(gè)”>”和”<”的區(qū)別。

處理R₁的時(shí)候，任意時(shí)刻處理P_k，我們希望找T中第一關(guān)鍵字大于某常數(shù)的第二關(guān)鍵字最小元素；處理R₂的時(shí)候，任意時(shí)刻處理P_k，我們要找的就是T中第一關(guān)鍵字小于某常數(shù)的第二關(guān)鍵字最小元素。

因而很容易發(fā)現(xiàn)，R₁和R₂可以和在一起處理。

這樣我們只要處理R₁+R₂、R₃+R₄這兩種情況即可。時(shí)間復(fù)雜度的常系數(shù)從8降低到了2。

我們按照這樣的方法建立的離散圖至多含有8n條邊。對(duì)該圖求最小生成樹(shù)的時(shí)間復(fù)雜度為O(nlogn)；之前建圖的復(fù)雜度也是O(nlogn)，所以總時(shí)間復(fù)雜度O(nlogn)。空間復(fù)雜度O(n)。

總結(jié)

這個(gè)題目最值得稱(chēng)道的地方就是“分區(qū)域”。“分區(qū)域”充分利用了平面性質(zhì)，結(jié)合一般情況下最小生成樹(shù)都具有的環(huán)切性質(zhì)，該方法取得了奇效。

我們研究問(wèn)題的時(shí)候也應(yīng)該注意充分利用已有信息。