Abstract
最近，許多實際的應用問題上，都牽涉到正交多邊形。我們發現把一個正交多邊形切成矩形的結構，有很多的應用，諸如在計算機圖學，影像處理，超大型積體電路設計，計算機輔助設計，及計算機輔助製造上。在本論文，首先研究一些現有的有關切成矩形的一些演算法，在這其中，我們發現(1) 如果要切成個數最少的矩形，目前最好的方法需要O（n5╱2）。(2) 其中有一個演算法，雖然需要O（n2） ，但可適於平行處理。然後我們提出了一個較快的演算法在O（n3╱2 logn） 之時間內能切成最少的矩形個數。此法是利用圖形理論的技巧，但不需要實際的去建造此問題的相對應圖形。最後我們提出了一個在正交多邊形尋找最近曼哈頓路徑的問題。此問題我們利用切成矩形的技巧在O（nlogn）之時間內就解決。