標題: 一個以矩形覆蓋多邊形的演算法
On covering polygons with rectangleseng
作者: 曾淑美
ZENG, SHU-MEI
張鎮華
陳秋媛
ZHANG, ZHEN-HUA
CHEN, QIU-YUAN
應用數學系所
關鍵字: 多邊形;演算法;矩形
公開日期: 1991
摘要: 用矩形來覆蓋多邊形是一個很重要的多邊形分解問題。在這篇論文中,我們將討論 兩個問題,一個是用矩形來覆蓋凸多邊形,另一個是用矩形來覆蓋簡單多邊形。對 這兩個問題我們都分別提出一個演算法,而這些演算法所產生的矩形個數最多是0( n log L/2D) ,它所用的時間是 0(n log n + n log L/2D),其中n代表多邊形的 點數,L/2D與多邊形的形狀有關,我們稱之為長寬比。當考慮用矩形來覆蓋凸多邊 形這個問題時,目前解決這個問題的最佳演算法它所產生的矩形個數最多會到達 0 (max {n□, n log L/2D }),而它所用的時間是 0(max {n□, n log L/2D }),所 以我們的演算法改進了目前最佳的演算法。
URI: http://140.113.39.130/cdrfb3/record/nctu/#NT802507002
http://hdl.handle.net/11536/56352
Appears in Collections:Thesis