一個以矩形覆蓋多邊形的演算法

Abstract

用矩形來覆蓋多邊形是一個很重要的多邊形分解問題。在這篇論文中，我們將討論 兩個問題，一個是用矩形來覆蓋凸多邊形，另一個是用矩形來覆蓋簡單多邊形。對 這兩個問題我們都分別提出一個演算法，而這些演算法所產生的矩形個數最多是0( n log L/2D) ，它所用的時間是 0(n log n + n log L/2D)，其中ｎ代表多邊形的 點數，L/2D與多邊形的形狀有關，我們稱之為長寬比。當考慮用矩形來覆蓋凸多邊 形這個問題時，目前解決這個問題的最佳演算法它所產生的矩形個數最多會到達 0 (max {n□, n log L/2D })，而它所用的時間是 0(max {n□, n log L/2D })，所 以我們的演算法改進了目前最佳的演算法。