Abstract
本論文主要探討動態的計算幾何問題，所謂動態是指所給予的幾何物件，如點，依照某時間函數運動而言。以往大部份的計算幾何問題所研究的幾何物件都固定在空間中的某個位置，我們稱之為靜態計算幾何問題。本論文討論了四個問題，前三個問題定義成「前處理－－查詢」（ｐｒｅｐｒｏｃｅｓｓｉｎｇ－ａｎｄ－ｑｕｅｒｙ）的形態，第四個定義成一典型的最佳化問題。前三個問題分別是「最小延展樹」（ｍｉｎｉｍｕｍ ｓｐａｎｎｉｎｇ ｔｒｅｅ）問題，「相對鄰居圖」（ｒｅｌａｔｉｖｅ ｎｅｉｇｈｂｏｒｈｏｏｄ ｇｒａｐｈ）問題和「范氏圖」（Ｖｏｒｏｎｏｉ ｄｉａｇｒａｍ）問題。第四個為「固定大小圓盤覆蓋問題」（ｆｉｘｅｄ•ｓｉｚｅ ｄｉｓｋ ｃｏｖｅｒｉｎｇ ｐｒｏｂｌｅｍ），對於前三個問題，我們的目標是希望在最佳的查詢時間下，如何讓前處理所需的時間和貯存前處理結果的空間儘量的減少。對於第四個問題，希望能找出處理時間短的計算方法。如果平面上有ｎ個點，每個點的ｘ，ｙ座標都是時間的ｋ一次多項式而ｋ是一個常數的話，對於動態最小延展樹問題，我們所提出的計算方法前處理時間為Ｏ（ｎ ｌｏｇ ｎ），貯存空間為Ｏ（ｍ），查詢時間為Ｏ（ｎ）。其中ｍ是指最小延展樹從ｔ＝０到ｔ＝∞所改變的次數，我們已證明ｍ≦Ｏ（ｎ ）。而動態相對鄰居圖問題的前處理時間為Ｏ（ｎ ｌｏｇｎ）貯存空間為Ｏ（ｎ ），查詢時間為Ｏ（ｎ）。動態范氏圖問題的前處理時間為Ｏ（ｎ ｌｏｇｎｌｏｇ* ｎ）貯存空間為Ｏ（ｎ ｌｏｇ* ｎ），查詢時間則為Ｏ（ｎ）。而對於固定大小圓盤覆蓋問題，我們找到的最好計算方法其時間為Ｏ（ｎ ｌｏｇｎ）。