一個分解簡單多邊形為一致單調多邊形的演算法

Abstract

在計算幾何學中，將多邊形分解成一些較簡單的形狀是一個重要且有趣的 問題。在這篇論文□，我們將討論如何將一個簡單多邊形分解成一致單調 多邊形，而且這些一致單調多邊形的個數必須是最少。Liu 和Ntafos在 1988 年提出了一個.blksq. 時間的演算法來解決上述問題；在這篇論文 □，我們將提出一個.blksq. 時間的演算法來解決這個問題。在以上的符 號中，n 是多邊形中所有頂點的個數，而 N是多邊形中大於 180度的頂點 的個數。如果 N是常數，則我們的演算法只要 O(n) 的時間，這將是最佳 的一個演算法。 Decomposing polygons into simpler shapes is an important and interesting problem in computational geometry. In this thesis, we shall pay our attention to the problem of partitioning a simple polygon into the minimum number of uniformly monotone parts. In 1988, Liu and Ntafos proposed an .blksq. time algorithm to solve this problem. In this thesis, we shall propose an .blksq. time algorithm for this problem. Here n is the number of vertices and N is the number of notches of the polygon. When N is bounded by a constant, our algorithm takes only O(n) time and this is optimal.