多邊形分解問題之研究

Abstract

在計算幾何學中有一個重要的研究方向就是多邊形的分解問題。在這篇論文中，我們 首先討論了如何將一個簡單多邊形分解成最少個數的三角形。假設△*(P)表示一個簡 單多邊形P 所需三角形的最少個數值，我們發現△*(P)=n+2w-d-2， 而且△*(P)滿足 不列條件：若w=0， 則（圖表省略） 在這些式子中，n 表示多邊形中端點的個數，w 表示多邊形中洞中的個數，而d 表示 多邊形中互不相依的退化三角形的最大個數值。同時，我們也提出了一個將不含洞的 簡單多邊形分解成最少個數的三角形的方法。這個方法所需的時間是O（n㏒2n + DK2 ）；其中，n 表示多邊形中端點的個數，D 表示多邊形中最多有多少個端點共線，而 K 則表示多邊形中最小退化三角形的個數。 接著，我們討論了如何將一個有洞的簡單多邊形分解成三角形。一個有n 個端點且沒 有洞的簡單多邊形可以在O(N)的時間內被分解成三角形。然而，當多邊形中有洞時， 則沒有任何已知的方法可以在O(Nn㏒n)的時間內將多邊形分解成三角形。因此，我們 提出了“預先去掉多邊形中的洞”的處理方式。同時，我們也提出了三個去掉多邊形 中的洞的快速方法。這三個方法所需的時間分別是O(n+h3/2 ㏒n)，O(n㏒n)及O(n2) ；其中n 表示多邊形中端點的個數，而h 表示多邊形中洞的個數。利用這個處理方式 ，我們發現當多邊形中洞的個數少於(n/㏒n)2/3時，這個多邊形就可以在O(n)的時間 內被分解成三角形而不再需要花費O(n㏒n) 的時間了。同時，我們也發現這個處理方 式可以在多項式的時間內將一些多邊形（例如，沒有四點共線的多邊形）分解成最少 個數的三角形。 最後，我們討論了如何在重疊的次數要最少的情況下，將一個簡單多邊形分解成矩形 。一個簡單多邊形可以被分解成互不重疊的三角形；然而，當一個簡單多邊形被分解 成矩形時，重疊卻無法避免。因此，我們提出了一個將簡單多邊形分解成矩形，同時 這些矩形之間的重疊次數必須要最少的方法。這個方法需要O(n'㏒n") 的時間，而它 適用於由k ×45°直線所組成的多邊形；其中，k 表示一個整數，n'等於3t/2s+n-1 ，n 表示多邊形中端點的個數，s 表示多邊形中互不相連的兩個邊之間的最短距離， 而t 表示多邊形的邊長總和。 /////// One of the major research efforts in the field of computational geometry focuses on polygon decomposition problems. In this thesis, we first strdy the problem of triangulating a simple polygon with the minimum number of triangles. Let △*(P) denote the minimum number of nondegenerate triangles required to triangulate a given simple polygon P. We show that △*(P)= n+2w-d-2 and △*(P)satisfies the following bounds: if w=0, then (圖表省略) Here n is the number of vertices, w is the number of holes, and d is the maximum number of independent degenerate triangles of the polygon. We also propose an algorithm with time complexity O(n㏒2n+DK2) for constructing the minimum triangulation of a simple hole0free polygon, where n is the number of vertices, D is the maximum number of vertices lying on the same line in the polygon and K is the number of minimally degenerate triangles of the polygon. The we investigate the problem of triangulating a simple polygon with holes. Triangulating a hole-free simple polygon with n vertices can be performed in O(n) time. However, no o(n㏒n) time algorithm is known when holes are allowed even if there is only one hole. We propose a new approach to this problem: removing holes from a simple polygon as a preprocessing step, and present three efficient algorithms to remove holes. The time complexities of these three algorithms are O(n+h3/2 ㏒n), O(n㏒n)and O(n2), respectively; here n is the number of vertices and h is the number of holes. We show that when the number of holes in the given polygon is less than (n/㏒n)2/3, by using this approach, triangulation can be done in O(n) time instead of O(n㏒n). We also show that this approach can be used to construct the minimum triangulations for a class of polygons (for example, polygons in which no four vertices are collinear) in polynomial time. Finally, we study the problem of decomposing a simple polygon into rectangles with the minimum number of overlappings. A simple polygon can be decomposed into triangles without overlapping, but it is not the case when a simple polygon is decomposed into rectangles. We propose an O(n'㏒n') time algorithm to cover a simple polygon which is bounded by k×45°lines with rectangles such that the overlapping of rectangles is minimized. Here k is an integer, n' is equal to 3t/2s+n-1, n is the nuber of vertices, s is the shortest distance between any two disjoint edges, and t is the total edgel length of the given polygon.