Abstract
在本篇論文中，我們對三個平面計算幾何學中的問題提出它們的即時 演算法。這三個問題分別是convex hull問題，最遠兩點問題，和最小覆 蓋圓問題。我們的演算法使用稱之為平行線包含策略的方法，對於每一個 新加入的點，只需要固定大小的時間去處理，就可以求得一個近似解。而 且對於空間的需求也只要固定的大小。雖然，我們求得的只是一個近似解 ，但是，我們證明出這個近似解可以非常地接近最佳解。本文分為六章： 第一章前言；在本章中，對於即時演算法的觀念與進展和本論文將處理的 三個平面計算幾何學中的問題的定義與已知的有關結果，都做了詳盡的介 紹。第二章介紹三個問題的即時演算法的基本策略，平行線包含策略。第 三章提出解決convex hull 問題的近似即時演算法；並且以凸多邊形的周 長總和做為衡量近似性的標準，我們證明出這個近似解可以非常地接近最 佳解。第四章提出解決最遠兩點問題的近似即時演算法；並且以兩個點間 的距離做為衡量近似性的標準，我們也證明出我們的解可以非常地接近最 佳解。第五章提出解決最小覆蓋圓問題的近似即時演算法；並且以圓的半 徑做為衡量近似性的標準，我們也證明出我們的解大於最佳解，但非常地 接近最佳解。最後一章是結論；我們相信做為基本策略的平行線包含策略 可以有更廣的應用。