直交多邊形分解之演算法和旅行推銷員問題

Abstract

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