標題: ON THE MINIMALITY OF POLYGON TRIANGULATION
作者: CHEN, CY
CHANG, RC
資訊科學與工程研究所
Institute of Computer Science and Engineering
公開日期: 1990
摘要: The problem of triangulating a polygon using the minimum number of triangles is treated. We show that the minimum number of triangles required to partition a simple n-gon is equal to n + 2w - d - 2, where w is the number of holes and d is the maximum number of independent degenerate triangles of the n-gon. We also propose an algorithm for constructing the minimum triangulation of a simple hole-free n-gon. The algorithm takes O(nlog2n + DK2) time, where D is the maximum number of vertices lying on the same line in the n-gon and K is the number of minimally degenerate triangles of the n-gon.
URI: http://hdl.handle.net/11536/4208
http://dx.doi.org/10.1007/BF01933206
ISSN: 0006-3835
DOI: 10.1007/BF01933206
期刊: BIT
Volume: 30
Issue: 4
起始頁: 570
結束頁: 582
顯示於類別:期刊論文


文件中的檔案:

  1. A1990EX83000001.pdf