Abstract
在本論文中, 我們將討論兩個計算幾何的問題。這兩個問題均可以歸類為直邊多邊形的最佳矩形分解問題。直邊多邊形的邊均平行於X 軸或Y 軸。分解問題可以依其所分解出的矩形是否重疊，而分為涵蓋問題與切割問題。若分解出的矩形可以重疊，便叫做涵蓋問題，若不能重疊，便叫做切割問題。直邊多邊形具有多種不同的形狀：凸形直邊多邊形，水平凸形直邊多邊形，垂直凸形直邊多邊形，簡聯直邊多邊形，覆聯直邊多邊形。本論文中討論的第一個問題是凸形直邊多邊形的涵蓋問題。我們提出了一個僅須線性時間的計算方法來角這個問題。線性時間是這個問題的下限，換言之，我們所提出的計算方法是最佳的方法。第二個問題是簡聯直邊多邊形的切割問題。我們提出了一個需要 O(nloglogn)時間的計算方法, 也較以往 O(n logn)的計算方法為佳。在 O(nloglogn)的計算方法中,我們以三解化為前處理，然后再求出最大配對及最大獨立集，最大配對及最大獨立集均可在 O(n) 時間內完成, 但因為三角化目前需要 O(nloglogn)的時間, 所以共需O(nloglogn) 的時間。這個計算方法若用來解水平凸，垂直凸或凸形直邊多邊形，因為三角化僅須 O(n) 的時間, 故在 O(n) 時間內可以全部解完, 當然也就是最佳解。除此之外，我們並證明了，覆聯直邊多邊形的分割問題的下限時間是 O(nlogn)。