Abstract
在日常生活中常有許多問題是去看守或是去照明ㄧ些物件或區域，例如在超級市場中放置監視攝影機、在起伏的地形上設置雷達監視系統又或是在起居室中安置照明設備。在我們的論文中我們將討論一些多邊形（Simple polygon）上的警衛問題及在二維地形上建看守塔的問題，我們的論文主要分成兩部份，一是討論在多邊形（Simple polygon）上的警衛問題，一是討論二維地形上建看守塔的問題。 多邊形（Simple polygon）上的警衛問題是源自於藝廊問題（Art gallery problems），一個警衛如果可以在多邊形中的線段上移動，我們稱它為行動警衛（Mobile guard），在論文的第一部份我們將討論三種不同移動自由度的行動警衛。第一、警衛對角線（Guard diagonal）：行動警衛可以在多邊形的對角線上移動而且多邊形內部的每一個點都可以被這行動警衛看到，第二、警衛弦﹙Guard chord﹚：行動警衛可以在多邊形的弦上移動而且多邊形內部的每一個點都可以被這行動警衛看到，第三、警衛邊界﹙Guard boundary﹚：行動警衛可以在多邊形的邊界上移動而且多邊形內部的每一個點都可以被這行動警衛看到。在這部份我們將提出一個找出最短對角線警衛的O(n α(n)) 時間演算法、一個找出最長警衛對角線的線性時間﹙linear time﹚演算法、一個找出最長警衛弦線性時間演算法以及一個找出最短警衛邊界O(n log n) 時間演算法。 在論文的第二部份我們將討論一些二維地形上建看守塔﹙Watchtower﹚的問題，一個二維地形是指ㄧ個由x的片段連續函數所定義出來的圖形，換句話說就是一個連續的線段只和垂直線交於一點。在電腦影像﹙Computer vision﹚及地理系統上有許多應用，在近幾年有許多關於地形上問題的研究，論文中我們將提出一個找出最小的看守塔的線性時間﹙linear time﹚演算法及一個最小和的兩個看守塔的O(n2) 時間演算法﹙相同的方法可用於找出最大最小的兩個看守塔﹚。