正交多邊形的凸四邊形化

Abstract

本論文所研究的是正交多邊形分割成最少的凸四邊形的問題。我們證明分割僅包含 n 水平或垂直共線的點的正交多邊形成為最少的凸四邊形的數目等於─ +w-1-d.我們 1.5 2 ' 同時提一個需時為Ｏ(ｎ ｌｏｇｎ)的演算法來建構這種正交多邊形的最少凸四邊 形分割法。這裡的ｎ和ｗ分別為所給正交多邊形的點數和洞的數目，ｄ則為和此多 邊形相關的一個圖的最大互不相依數。我們也推導了一些一般正交多邊形的性質。