Abstract
畫廊警衛問題的定義是這樣的：給予一個多邊形，決定一種在此多邊形內部的警衛配置，使得多邊形內部的任何地方至少有一個警衛看到，所謂一個配置於點p 的警衛能看到多邊形內部的一點q ，是指連結p 和q 這兩點的線段完全落在此多邊形的內部。先後有人證明這個問題只需要「n/3 」和「n/4 」個警衛即足以分別看管整個一般多邊形及直交多邊形，其中n 是多邊形的頂點個數，對應於上述證明結果的計算方法也已相繼發表。然而「n/3 」和「n/4 」只是個上限值，一般而言，並不需要這麼多個警衛，因此如何求得最少的警衛數是個值得研究的課題，很不幸的，在一般多邊形上求最少畫廊警衛問題已被證明為NP-hard 。在直交多邊形上尚未得知是否為NP-complete 或NP-hard 。在此篇論文中我們將多邊形限定為直交多邊形，試圖解答其最少畫廊警衛問題，首先我們將直交凸多邊形區分為四種類別。其中兩種類別只需要兩個警衛，另外兩種類別則需要多個警櫥，我們提出一個計算方法以解決之，其時間是線性的，但沒能求得最佳解。