本篇論文主要探討在影像處理、計算機圖學、圖型識別以及超大型積體電路上時常使
用的直交多邊形（rectilinear polygon ）。我們將討論兩種分解直交多邊形為矩形
的問題。首先，我們考慮將直交多邊形分割成不重疊的矩形；其次，在矩形可以重疊
的情況下，我們先考慮一種稱為直立的直交多邊形（vertically convex ），這種多
邊形已經證明存在有多項式之計算時間的演算法，然後再討論切割一般的直交多邊形
之啟發式演算法。最後我們將討論旅行推銷員問題用以找出較短的路徑繞完由切割找
出來的矩形。
|