冬令營(yíng)講義l1-metric問題研究

1、一類基于曼哈頓距離問題的研前系統(tǒng)(L1-Metric Distance)。本文側(cè)重于基于曼哈頓距離系統(tǒng)的最優(yōu)化問題和最小生正1. 一些基本 xi yi nnS =p1, p2, , pnSpiSpj，使得 pi pj min pi pk pks 意一個(gè)點(diǎn)v，以點(diǎn)v 作為原點(diǎn)建立坐標(biāo)系。位于坐標(biāo)系第一象限的點(diǎn)都有x xv y yv（也可以將號(hào)改成，因?yàn)樽鴺?biāo)軸上的點(diǎn)不具有特殊性v的距離為(xyxv + yv)。因此在第一象限中v的最近點(diǎn)，只需要尋找(xy)最小的點(diǎn)。同理，對(duì)于其他象限的點(diǎn)，兩點(diǎn)之間的距離也可以去符號(hào)轉(zhuǎn)化成線性的計(jì)算式。如圖 1 所示：x xv,y (xv,x xv,y x xv,y

2、 x xv,y 將所有點(diǎn)的橫坐標(biāo)進(jìn)行離散，記作(x1, x2, x3,xn)。樹狀數(shù)組用于記錄區(qū)間(xi, xn中 x + y 最小的點(diǎn)，初始化為 0。 S pipi xj。在樹狀數(shù)組中查詢(xj,xn中 x+y之和最小的頂點(diǎn)，這個(gè)頂點(diǎn)即為pi 的第一象限最近點(diǎn)。將pi 的x+y 坐標(biāo)和到樹狀郵局問 n S =p1, p2, , pnm Q=q1, q2, , qmQqiSqiL1-Metric的點(diǎn)染上不同顏色（相同顏色的區(qū)域一定是連續(xù)的1 這個(gè)例子：將圖1與里得距離的Voronoi圖比較發(fā)現(xiàn)，這些區(qū)域都是由平行坐標(biāo)軸和對(duì)角線的坐標(biāo)軸的，如圖 4。這些區(qū)域的邊界為什么會(huì)平行于坐標(biāo)軸呢？首先考慮

3、只有一個(gè)點(diǎn)的區(qū)域。令點(diǎn)集 N 中可以將平面看成一個(gè)有限的矩形。如圖 5 所示。uv因?yàn)?，?duì)于綠域中的任意點(diǎn)w，其到u1的距離|wu1|=xwxu1+yu1yw=(xwxv)+(xvxu1)yu1yvyvyw|wv|vu1|，同理|wu2|wv|vu2|。如果|vu2|vu1| l2l1，那么綠域中所有點(diǎn)的最近點(diǎn)為u1，否則最近點(diǎn)為u2。因此v 的最近點(diǎn)就是綠域中可見，當(dāng)點(diǎn)集N中的點(diǎn)多于2 個(gè)時(shí)，染域都可以用點(diǎn)數(shù)為2 時(shí)的方法，將矩形區(qū)每個(gè)點(diǎn)的坐標(biāo)作為分界線，將平面分割成 nn 個(gè)矩形區(qū)域。如圖 7：nn相同。因?yàn)閷?duì)于一個(gè)矩形區(qū)域(x1y1x2y2x1y1)為矩形的左上角，(x2y2)為矩形右下

4、角)，區(qū)域中，點(diǎn)(x1, y1)的最近點(diǎn)就是矩形區(qū)域(x1, y1, x2, y2)所有點(diǎn)最近點(diǎn)。點(diǎn)在哪個(gè)區(qū)域便可以求得最近點(diǎn)。預(yù)處理求每個(gè)區(qū)域的最近點(diǎn)可以用動(dòng)態(tài)規(guī)劃的方式來求解。對(duì)于一個(gè)矩形x11Nx1y 1域中的點(diǎn)，可以分成三部分考慮：xx1N 1 矩形（黃色矩形）v N v。(i(i,v(i-1,(i,j-(i-1, j- fi, jfi, jmaxf1, xi, j yi, 預(yù)處理求得f 函數(shù)之后。查詢?nèi)我恻c(diǎn)v 在第二象限的最近點(diǎn)，只需要通過哈希表或二分確v所在的矩形ijxvyvfijv到最近點(diǎn)的距離。預(yù)處理的時(shí)間復(fù)雜度為 O(n2)。單個(gè)點(diǎn)查詢的時(shí)間復(fù)雜度為 O(1)。所以總的時(shí)間復(fù)

5、雜度為 O(n2)-O(m)，這還是一個(gè)詢問算法。由于要存下 f 函數(shù)，所以上述算法的空間復(fù)雜度為 O(n2)。優(yōu)上述算法的空間耗費(fèi)比較大，所以影響了實(shí)際效率。上述算法將整個(gè)平面分成了 nn個(gè)矩形區(qū)域，由于實(shí)現(xiàn)的是算法，所以必須把n2 個(gè)區(qū)域全都保存下來。如果沒有算法的要求，那么不必要保存所有區(qū)域的f函數(shù)，類似于最近問題可以進(jìn)行如下改進(jìn)：首先仍然將平面進(jìn)行離散，用樹狀數(shù)組 fi函數(shù)。然后從第 1 行開始掃描：計(jì)算i fi函數(shù)，由于第i fi可以從fi-1推導(dǎo)，所以直接更新fi 1得到fi：枚舉在第i 行上點(diǎn)集N 中的點(diǎn)u，將點(diǎn)u 的坐標(biāo)和xu yu到fi 1中。在第1 步中用樹狀數(shù)組的f 函數(shù)

6、，每次更新的時(shí)間復(fù)雜度為O(logn)，而最多更新nfO(nlogn)。同時(shí)在執(zhí)行過程中每次只需要保存一f函數(shù)，空間復(fù)雜度為 O(n)。預(yù)處理中，利用桶排序?qū)點(diǎn)集中的點(diǎn)到每一行所代表的桶中，這樣完成第2步枚舉所有點(diǎn)的時(shí)間復(fù)雜度為 O(m)。而利用樹狀數(shù)組查詢每個(gè)點(diǎn)最近距離的時(shí)間復(fù)雜度為 O(logn)。所以第二步總的時(shí)間復(fù)雜度為 O(mlogn)。平面中給出有 n 個(gè)點(diǎn)的集合 S，點(diǎn)集 S 的曼哈頓距離最小生成樹是指：含有長(zhǎng)度之和最n 1 TS，邊的長(zhǎng)度定義為兩端點(diǎn)之間的曼哈頓G=(VE)G 的最小生成樹，通常用 Prim 算法可以達(dá)到 O(n2)的時(shí)間復(fù)雜度，而 Kruscal 為 O(m

7、logn)。本題若直接套用任意圖的最小生成樹算法，由于是建立的是完全圖，所以時(shí)間復(fù)雜度為 O(n2)?；仡櫰矫嫔系睦锏镁嚯x最小生成樹的解決，是利用了Delaunay三角剖分，建立了邊數(shù)只有 O(n)級(jí)別但至少包含一棵最小生成樹的子圖，然后利用 Kruscal 算法，在 O(nlogn)的時(shí)間復(fù)雜度下完成對(duì)最小生成樹的求解。而 Delaunay 三角剖分，是定義于 Voronoi 圖的對(duì)的。因此，解決曼哈頓距離的生成樹問題難以利Delaunay三角剖分，不過，下面將要介首先引出一個(gè)概念spanninggraph（暫譯為生成圖 樹。其中一個(gè)性質(zhì)是最小割性質(zhì)(cut property)：最小生成樹上

8、的每條邊都將圖分成了兩個(gè)點(diǎn)另一個(gè)概念：唯一性(uniqueness property)。2. sRsR中的所有直線構(gòu)成。如9(a)所示。這里R1R8為由兩條射線構(gòu)成的半平面（包括其中條射線。如圖 9(b)所示。下面證明八劃分具有唯一性。 對(duì)稱得到，所以下面將只證明域 R1 具有唯一性。x xs xy xs |sp|pq|pq|ypyq的情況：求平面八劃分中的最近點(diǎn)，與上文中所有點(diǎn)最近問題略十分相似，不妨回到這個(gè)問 題，看是否存在借鑒之處。在所有點(diǎn)最近問題中，對(duì)于每個(gè)點(diǎn)，是將平面劃分成四個(gè)域 考慮的。例如，在 s 點(diǎn)的第一象限域中，所有點(diǎn)的范圍滿足 x xs, y ys。因此在求s 點(diǎn)第一 象限

9、的最近點(diǎn)時(shí)，是按照從 y 軸從大到小，y 坐標(biāo)相同的按 x 從大到小這樣的順序，將點(diǎn) 樹狀數(shù)組的。也就是說，在查詢 s 點(diǎn)的最近點(diǎn)之前，所有滿足 x xs, y ys 的點(diǎn)都已經(jīng) 要解決平面八劃分中的最近點(diǎn)問題，主要是找到一個(gè)滿足完備性和純粹性的點(diǎn)序R1中的最近點(diǎn)的算法。對(duì)于一個(gè)待查s，sR1xxsxyxsysxy從小到大排序，xyx10s的最近點(diǎn)時(shí)，只(xs+1,s按xy 從小到大樹狀數(shù)psR1s p R5R1域中所連接的邊，已經(jīng)包含了在 R5 域中所連接的邊。將所有點(diǎn)的橫坐標(biāo)進(jìn)行離散，記作(x1x2x3,xn)。樹狀數(shù)組用于記錄區(qū)間(xixn)中 x + y 最小的點(diǎn)，初始化為 0。S pipi xj。在樹狀數(shù)組中查詢(xj,xn中 x+y之和最小的頂點(diǎn)qi，這個(gè)頂點(diǎn)即為pi R1 域最近點(diǎn)。然后pi 是否qi R5 域已記錄的最近點(diǎn)更近，若更近，則更新 qi 在 R5 域的最近點(diǎn)。最后將 pi 的x+y 坐標(biāo)和到樹狀O(nlogn)，空間復(fù)雜度O(n)。而生成圖的邊數(shù)為 O(n)級(jí)別，用 Kruscal 求最小生成樹為 O(nlogn)的時(shí)間復(fù)雜度。因此，求曼哈頓距離的最小生成樹可以在 O(nlogn)的時(shí)間復(fù)雜度下完成。 問題 3 中的求