李 麗, 張遠平, 李 鵬

(蘭州理工大學(xué)計算機與通信學(xué)院，中國 蘭州 730050)

多邊形搜索是計算幾何中的一類基本問題，這類問題考慮的是如何利用一個或多個移動的搜索者(搜索者有不同的視覺范圍)對一個多邊形進行搜索以便檢測到移動的入侵者．搜索者和入侵者均可用一個點表示，都可以在多邊形區(qū)域內(nèi)連續(xù)、任意地移動．文獻[1]中提出了各種不同的搜索者模型．對于任意的一個整數(shù)k≥1，k線搜索者(k-searcher)可以通過發(fā)出束光進行搜索，全視覺搜索者(∞-searcher)的視覺范圍為360°，邊界單線搜索者只能沿多邊形的邊界移動且只能發(fā)出一束光．

多邊形搜索問題[1]最初由Suzuki和Yamashita在1992年提出．由于應(yīng)用廣泛，如航海、安全防御、目標(biāo)探測和追蹤等等，該問題得到很多關(guān)注[2-3]．2000年Lavalle提出了一種基于可視圖思想的算法[4]，以此來檢測一個多邊形是否可被一個邊界單線搜索者搜索，其方法需要O(n2)的時間和空間．2003年Tan將上述時間復(fù)雜度降到O(nlogn)，空間復(fù)雜度降到O(n)[5]，但證明過程比較復(fù)雜．2006年Kamada利用可視圖的思想證明了3種不可被一個邊界單線搜索者搜索的模型[6]，雖然時間復(fù)雜度仍為O(nlogn)，但其證明過程比文獻[5]的簡單．2009年Tan給出了一些檢測多邊形是否可被邊界單線搜索者搜索的充分條件[7]，利用這些條件檢測多邊形的可搜索性只需O(n)的時間和空間，但這些檢測條件的證明過程相當(dāng)復(fù)雜．

本文給出了一些檢測多邊形是否可被邊界單線搜索者搜索的特征，這些特征類似于文獻[6]中提出的，但采用不同的定義方式和證明方法將其時間復(fù)雜度從O(nlogn)降到O(n)．此時間復(fù)雜度是檢測多邊形的邊界單線搜索性的下界，已不可能再優(yōu)化．同時，這些特征由文中所構(gòu)造的簡化骨架V圖論證，其證明過程比文獻[7]的簡潔．

1 基本概念與結(jié)果

對于搜索者s和其光束點f以及任意邊界點p，如果滿足：s和f從p開始分別沿?P逆時針和順時針移動，在保持s和f相互可見的情況下，它們無法繼續(xù)向前移動，則稱p為死鎖點．如圖2中d即為一個死鎖點．

設(shè)P為一個簡單多邊形，u和v為P中兩個不同頂點，L和R分別表示?P上從u到v的順時針和逆時針邊界鏈．如果L和R相互勉強可見，即L上每一點從R上某些點可見，反之亦然；則稱P為關(guān)于點對(u,v)的LR可見多邊形．

假設(shè)r∈P,q1,q2∈?P3點共線，如果滿足：①點q1從r可見；②邊界?Pcw(q1,q2]上的所有點從r都不可見；③每個包含q2的開區(qū)間，一定包含從r可見的另一點，則稱(q1,q2)形成一個相對于r的左間隔邊[9]，如圖3．右間隔邊定義類似．左右間隔邊統(tǒng)稱為間隔邊．

圖1 反射點r形成的向前向后擴展點 圖2 由反射點形成的(非)冗余組成 圖3 相對于r的左間隔邊 圖4 (a)由c,d形成的同側(cè)雙切線(b)c,d形成的異側(cè)雙切線

從任意點開始，沿順時針方向測量邊界的總長度，記為|?P|．對于任意實數(shù)x，總可以找到唯一的整數(shù)k，使得0≤x-k|?P|≤|?P|，因此x對應(yīng)于邊界?P上的一點．

可視空間(簡稱V空間)記為V[8]，它包括射線y=x(開始線S)和y=x-|?P|(目標(biāo)線G)中間所夾的無限區(qū)域，如圖5所示，圖中D=|?P|．

假設(shè)p=(a,b)∈V，q=(c,d)∈V，若b>d，則稱p(q)在q(p)的北(南)邊，類似地，若a>c，則稱p(q)在q(p)的東(西)邊[8]．

多邊形的可視圖(簡稱V圖)[8]是在V空間中將部分區(qū)域用灰色表示且滿足：一個點p(x,y)∈V是灰色的當(dāng)且僅當(dāng)x和y不能相互可見．

對于任意點p=(a,b)∈V，觀察其關(guān)于射線y=x的對稱點p′(b,a)，因為a與a-|?P|在?P上表示同一個點，且b與b+|?P|在?P上也表示同一個點，所以p=(a,b)∈V是灰色的當(dāng)且僅當(dāng)p1=(b,a-|?P|)∈V和p2=(b+|?P|,a)∈V也是灰色的．因此圖5中p與p1、p2兩點是對稱的．特殊地，S上的點(a,a)與G上的點(a,a-|?P|)和(a+|?P|,a)也是對稱的．

以下說明怎樣將一個簡單多邊形用V圖表示，多邊形中的不可見區(qū)域都是由反射點造成的，因此在V圖中只考慮反射點的信息，從而簡化操作．首先在多邊形邊界?P上標(biāo)識出每個反射點v的向前擴展點Forw(v)和向后擴展點Back(v)；然后從任意一個邊界點開始，對?P上的所有反射點和每個反射點對應(yīng)的向前與向后擴展點按順時針排序；再在V圖中按照它們在原多邊形中的排序位置用坐標(biāo)表示出來，V圖中的原點對應(yīng)排序的始點．

V圖中每個反射點都可形成2個對稱的灰色區(qū)域，此灰色區(qū)域稱為障礙物[8]．與射線S相切的障礙物為東南(簡寫為SE)障礙物，與射線G相切的為西北(簡寫為NW)障礙物．如圖6所示，反射點r對應(yīng)一個東南障礙物SE(r)和一個西北障礙物NW(r)，SE(r)有2條線段，一條水平向右延長到Forw(r)(稱為向東線)，一條垂直向下延長到Back(r)(稱為向南線)．對應(yīng)地，NW(r)也有2條線段，一條水平向左延長到|?P|+Back(r)(稱為向西線)，一條垂直向上延長到Forw(r)(稱為向北線)．稱這些線段為V圖的骨架線段．

圖5 可視空間 圖6 由反射點r形成的SE和NW障礙物

由于可搜索多邊形的主要信息都包含在V圖中反射點所對應(yīng)的骨架線段中，所以將V圖中的每個反射點所對應(yīng)的障礙物用兩條骨架線段來代替，這樣構(gòu)造的圖稱為骨架V圖[8]．圖8為圖7所對應(yīng)的骨架V圖，圖7中的反射點1在V圖中對應(yīng)障礙物SE(1)和NW(1)，而在骨架V圖中SE(1)對應(yīng)一條向東骨架線段延長到Forw(1)和一條向南骨架線段延長到Back(1)．由對稱性可知，NW(1)也同樣對應(yīng)兩條骨架線段．其他反射點的情形類似．

為簡化證明，在骨架V圖中只表示多邊形中有雙切線的反射點的信息，忽略其他點的信息．若兩反射點u,v具有同側(cè)雙切線，則表示為S(G)上u,v所對應(yīng)的骨架線段相交；若兩反射點u,v具有異側(cè)雙切線，則表示為S(G)上u對應(yīng)的骨架線段與G(S)上v對應(yīng)的骨架線段相交，這樣構(gòu)造的圖稱為簡化骨架V圖．圖9為圖7所對應(yīng)的簡化骨架V圖．

圖7 簡單多邊形 圖8 圖7對應(yīng)骨架V圖 圖9 圖7對應(yīng)簡化骨架V圖

在V圖中，合法的搜索路徑是從S上的一點開始順著白色的區(qū)域可以到達G上的一點，并且可從右到左穿過障礙物．在骨架V圖表示為可從右到左穿過垂直的骨架線段[4]．

定理1[4]一個給定的多邊形可被一個邊界單線搜索者搜索，當(dāng)且僅當(dāng)在其V圖中存在一條合法的搜索路徑．

定理2[4]一個給定的多邊形可被一個邊界單線搜索者搜索，當(dāng)且僅當(dāng)在其骨架V圖中存在一條合法的搜索路徑．

簡化骨架V圖是根據(jù)雙切線和V圖的關(guān)系簡化而來的，故由定理1，2可得出如下結(jié)論．

定理3一個給定的多邊形可被一個邊界單線搜索者搜索，當(dāng)且僅當(dāng)在其簡化骨架V圖中存在一條合法的搜索路徑．

簡化骨架V圖不但構(gòu)造簡單，而且在其中尋找一條合法搜索路徑也很容易．以下給出了單線搜索多邊形與LR可見多邊形的關(guān)系和一些相關(guān)的定理．

定理4[1]若多邊形P可被一個單線搜索者搜索，則P一定是LR可見多邊形．

定理5[10]確定一個多邊形是否為LR可見多邊形只需O(n)的時間，并且可在O(n)的時間內(nèi)計算出LR可見多邊形中所有非冗余的組成．

定理6[11]判斷所有的點x是否為死鎖點只需O(n)的時間，由此可以確定多邊形P是關(guān)于點對(x,y)的LR可見多邊形．

2 檢測多邊形是否可搜索的特征

為敘述方便，先簡述文獻[6]中的一些概念，但方式略有不同．

定義1兩個可見的反射點u,v有非冗余的逆時針(向前)組成，稱u,v構(gòu)成單右雙切線．

定義2兩個可見的反射點u,v有非冗余的順時針(向后)組成，稱u,v構(gòu)成單左雙切線．

定義3對于多邊形中3個相互可見的反射點u,v,w(順時針次序)和?P上的一點p，若滿足：①p,w∈P[v,Back(v)]；②p?P[u,Back(u)]且p?P[w,Back(w)]；③P[u,Back(u)]和P[w,Back(w)]是非冗余的，則稱點p存在一條雙右雙切線．如圖10．

圖10 雙右雙切線 圖11 雙左雙切線 圖12 特殊多邊形

定義4對于多邊形中3個相互可見的反射點u,v,w(順時針次序)和?P上的一點p，若滿足：①p,v∈P[w,Forw(w)]；②p?P[u,Forw(u)]且p?P[v,Forw(v)]；③P[u,Forw(u)]和P[v,Forw(v)]是非冗余的，則稱點p存在一條雙左雙切線．如圖11．

定理7一個多邊形P不可被一個邊界單線搜索者搜索，當(dāng)且僅當(dāng)P中存在以下某一情形：

(C1)多邊形的每個邊界點p都在一條同側(cè)雙切線的內(nèi)側(cè)．

(C2)多邊形的每個邊界點p都存在一條雙右(左)雙切線．

(C3)多邊形的一些邊界點在同側(cè)雙切線的內(nèi)側(cè)，其余的每個邊界點都存在一條雙右(左)雙切線．

證(1)充分性．若P中存在(C1)～(C4)中的某一種情形，假定P中共切線的反射點有4個且滿足條件(C1),其對應(yīng)的簡化骨架V圖如13(a)所示，從圖中可以看出不存在一條合法的搜索路徑.P中若存在(C2)，(C3)或(C4)的情形，圖13(b),(c)和(d)分別表示了P中有3個滿足條件(C2)，有5個滿足條件(C3)和3個滿足條件(C4)的共切線的反射點所對應(yīng)的簡化骨架V圖，3個圖中都不存在一條合法的搜索路徑.推廣到P中有多個滿足條件(C1)，(C2)，(C3)或(C4)的共切線的反射點的情形也相同.由定理3可知，P不可被一個邊界單線搜索者搜索．

a b c d圖13 多邊形滿足定理7中條件的簡化骨架V圖示例，分別為a.(C1);b.(C2);c.(C3);d.(C4)

(2)必要性．如果一個多邊形P不可被邊界單線搜索者搜索，由定理3可知，P對應(yīng)的簡化骨架V圖中一定不存在一條合法的搜索路徑，即簡化骨架V圖中出現(xiàn)以下情形：

1) 開始線S上的所有邊界點都處于陷阱區(qū)域(搜索者進入此區(qū)域無法跳出，如圖14(a)中S線上的u,v區(qū)域和圖14(c)中S線上的w,v區(qū)域)，即不存在一點可以作為搜索的入點．這種情形只出現(xiàn)在P的邊界點在同側(cè)雙切線的內(nèi)側(cè)或者存在一條雙左雙切線．

2) 目標(biāo)線G上的所有的邊界點都處于不可達區(qū)域(如圖14(a)中G線上的u,v區(qū)域和圖14(b)中G線上的w,v區(qū)域)，即不存在一點可以作為搜索的完成點．這種情形只出現(xiàn)在P的邊界點在同側(cè)雙切線的內(nèi)側(cè)或者存在一條雙右雙切線．

3)S上有開始點，G上也有完成點，但從S上的所有入點都不可到達G上的某點，即出現(xiàn)(C4)所表示情形．

上述情形1)、2)對應(yīng)條件(C1)，(C2)或(C3)，所以P不可被邊界單線搜索者搜索，一定存在(C1)到(C4)中的某一種，且只存在這些情形．

圖14 (a)同側(cè)雙切線的簡化骨架V圖；(b)雙右雙切線的簡化骨架V圖；(c)雙左雙切線的簡化骨架V圖

定理8利用定理7檢測一個給定的有n個頂點的多邊形P是否可被一個邊界單線搜索者搜索只需O(n)的時間和空間．

證首先檢測多邊形P是否為LR可見多邊形，只需線性時間[10]，若P不是LR可見多邊形，由定理4可知，P不可被一個單線搜索者搜索．若P是LR可見多邊形，再用定理7檢測．下面給出了如何在O(n)的時間和空間內(nèi)驗證定理7中特征的證明過程．

對于(C1)，由定理6可知，可在O(n)的時間內(nèi)檢測出所有的搜索入點p是否為死鎖點，檢測p是否死鎖即檢測p是否在一條同側(cè)雙切線的內(nèi)側(cè)，因此檢測完所有的入點p是否都存在一條同側(cè)雙切線且p在其內(nèi)側(cè)也只需O(n)的時間．

對于(C2)，首先檢測所有的非冗余的順時針(逆時針)組成需O(n)的時間，再依次檢測下列條件：①是否存在一個反射點w及任意一個邊界點p在另一個反射點v的順時針(逆時針)組成中，只需O(1)時間；②是否存在一個與v可見的反射點u，并且u,v構(gòu)成非冗余的順時針(逆時針)組成且不包括p，只需O(1)時間．即檢測P的任意一個邊界點p是否存在一條雙右(左)雙切線只需O(1)時間．所以檢測完所有的邊界點共需O(n)的時間．

對于(C3)，它是(C1)和(C2)的組合，檢測多邊形中的邊界點是否為死鎖點只需O(n)時間，然后再檢測除死鎖點之外的其余邊界點是否都存在雙右(左)雙切線也只需O(n)時間，所以檢測完多邊形的所有邊界點需O(n)時間．

對于(C4)，可以在檢測邊界點p是否死鎖時外加一個限制條件，若檢測到一個邊界點p在由反射點u,v構(gòu)成的同側(cè)雙切線的內(nèi)側(cè)，則再檢測此雙切線的內(nèi)側(cè)是否存在另一反射點w，使得w形成的順時針(逆時針)組成與u(v)形成的順時針(逆時針)組成構(gòu)成非冗余的關(guān)系，這只需O(1)時間，因為所有的非冗余的順時針(逆時針)組成都在O(n)的時間內(nèi)已檢測出．若存在這樣的w，則斷定此多邊形不可被一個邊界單線搜索者搜索；若本區(qū)域不存在這樣的w，則繼續(xù)在下一死鎖區(qū)域用同樣的方法檢測．檢測完所有的入點p是否為死鎖點只需O(n)的時間[11]，所以(C4)的檢測時間為O(n)．

綜上所述，利用定理7檢測一個多邊形是否可被一個邊界單線搜索者搜索只需O(n)的時間，并且由上述證明過程可以看出，定理7中特征的驗證所需空間復(fù)雜度也為O(n)．

3 總結(jié)

本文給出了一些檢測多邊形是否可被一個邊界單線搜索者搜索的特征，并利用本文構(gòu)造的簡化骨架V圖進行證明，比文獻[7]的證明簡單，將文獻[6]的時間復(fù)雜度從O(nlogn)降到O(n)．是否可將本文的證明方法應(yīng)用到兩個搜索者模型中，尚待進一步研究．

參考文獻：

[1]SUZUKII,YAMASHITAM.Searchingforamobileintruderinapolygonalregion[J].SIAMJournalonComputing, 1992, 21(5): 863-888.

[2]PARKSM,LEEJH,CHWAKY.Acharacterizationoftheclassofpolygonssearchablebya1-searcher.TechnicalReportCS/TR-2000-160[R].Kaist:KoreaAdvancedInstituteofScienceandTechnology, 2000.

[3]TANX.Searchingasimplepolygonbyak-searcher[J].LectureNotesinComputerScience, 2000, 1969/2000:275-319.

[4]LAVALLESM,SIMOVB,SLUZKIG.Analgorithmforsearchingapolygonalregionwithaflashlight[J].InternationalJournalofComputationalGeometryandApplications, 2002, 12(1/2): 87-113.

[5]TANX.Acharacterizationofpolygonalregionssearchablefromtheboundary[J].LectureNotesinComputerScience, 2005, 3330/2005:200-215.

[6]KAMEDAT,ZHANGJZ,YAMASHITAM.Simplecharacterizationofpolygonssearchableby1-searcher:proceedingsofthe18thCanadianconferenceoncomputationalgeometry,Kingston,Canada, 2006[C].Kingston:[s.n.],2006.

[7]TANX.Searchingapolygonalregionbyaboundarysearcher[J].JournalofComputerScienceandTechnology, 2009, 24(3): 505-516.

[8]KAMEDAT,YAMASHITAM,SUZUKII.On-linepolygonsearchbyasix-stateboundary1-searcher[R].TechnicalReportCMPT-TR2003-07,Canada:SimonFraserUniversity, 2003.

[9]SIMOVB,LAVALLESM,SLUTZKIG.Acompletepursuit-evasionalgorithmfortwopursuersusingbeamdetection:proceedingsofIEEEinternationalconferenceonroboticsandautomation,WashingtonDC,USA, 2002[C].WashingtonDC:[s.n.],2002.

[10]DASG,HEFFERNANPJ,NARASIMHANG.LR-visibilityinpolygons[J].ComputationalGeometryTheoryandApplications, 1997, 7(1): 37-57.

[11]BHATTACHARYABK,MUKHOPADHYAYA,NARASIMHANG.Optimalalgorithmsfortwo-guardwalkabilityofsimplepolygons[C]//DEHNEF,SACKTR,TAMASSIAR.AlgorithmsandDataStructures, 7thInternationalWorkshop,WADS2001,LNCS2125.NewYork:Springer-Verlag, 2001, 438-449.