Abstract
美術館警衛問題(Art Gallery Problem)是Victor Klee於1973年提出的。他問道：需要多少警衛才能看管整個美術館﹖美術館以多邊形表示，警衛是多邊形內固定不動的點。如果多邊形內的某一點和某警衛相連的線段在此多邊形內部，則稱此點被此警衛看見。從那時開始，許多人研究美術館警衛問題的變型問題，尤其是在O'Rourke於 1987年出版了此問題的專書〝美術館警衛問題之定理與演算法〞之後。在此篇論文中，我們引進了固定不動的警衛之間的互助合作關係，以一個警衛可見性圖形表示。在此圖形中，頂點表示警衛，兩頂點間有線段相連表示相對應的兩警衛彼此互相可見。我們提出一個新的一類的美術館警衛問題，稱之為〝每個合作群警衛數大於k之最少警衛問題(the Minimum k-Cooperative GuardsProblem)〞，簡稱MkCG問題。這個問題要求看見整個多邊形的警衛數最少，並且所得到的警衛可見性圖形的每個不相連的子圖形的警衛數必須大於k。在這個新的問題中，有兩個特別的子問題：其中警衛之間最鬆散的合作關係是令k=1，亦即，警衛可見性圖形沒有任何孤立的頂點。我們稱此問題為〝最少低度合作警衛問題(the Minimum Weakly CooperativeGuards Problem)〞，簡稱MWCG問題。另外，警衛之間最嚴密的合作關係是警衛可見性圖形本身就是一個連結圖形。我們稱此問題為〝最少高度合作警衛問題(the Minimum Strongly Coopera- tive Guards Problem)〞，簡稱MSCG問題。我們證明了在簡單多邊形上的MkCG問題為NP－難的問題。因此，我們嘗試在一類特殊的多邊形：h螺旋(h-spiral)多邊形上，當h=1和 2時，解決此問題。所謂h螺旋多邊形是指一個簡單多邊形其邊界可以被分割成h個凹形鏈和h個凸形鏈。對於單螺旋多邊形，我們提出了最佳線性演算法以解決MWCG和 MSCG問題，也提出一個O(kn)時間的演算法以解決MkCG問題，當k>1時，其中n是多邊形的頂點個數。當k是輸入資料的一部份時，這是個最佳線性演算法。我們也在單螺旋多邊形上解決了〝強制型MSCG問題〞。這個強制型的問題和原來的MSCG問題只有一點不同，就是有一個事先指定的警衛必須在解答之中。我們提出了一個最佳線性演算法以解決此問題。對於雙螺旋多邊形，我們提出了一個最佳線性演算法以解決 MSCG問題。對於不同的警衛問題所需的警衛數，我們證明了，對於相同的單螺旋和雙螺旋多邊形，MkCG問題所需要的警衛數頂多是美術館警衛問題所需要的警衛數的兩倍。