ON THE MINIMALITY OF POLYGON TRIANGULATION
| dc.citation.epage | 582 | en_US |
| dc.citation.issue | 4 | en_US |
| dc.citation.spage | 570 | en_US |
| dc.citation.volume | 30 | en_US |
| dc.citation.woscount | 2 | |
| dc.contributor.author | CHEN, CY | en_US |
| dc.contributor.author | CHANG, RC | en_US |
| dc.contributor.department | 資訊科學與工程研究所 | zh_TW |
| dc.contributor.department | Institute of Computer Science and Engineering | en_US |
| dc.date.accessioned | 2014-12-08T15:05:40Z | |
| dc.date.available | 2014-12-08T15:05:40Z | |
| dc.date.issued | 1990 | en_US |
| dc.description.abstract | 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. | en_US |
| dc.identifier.doi | 10.1007/BF01933206 | en_US |
| dc.identifier.issn | 0006-3835 | en_US |
| dc.identifier.journal | BIT | en_US |
| dc.identifier.uri | http://dx.doi.org/10.1007/BF01933206 | en_US |
| dc.identifier.uri | https://ir.lib.nycu.edu.tw/handle/11536/4208 | |
| dc.identifier.wosnumber | WOS:A1990EX83000001 | |
| dc.language.iso | en_US | en_US |
| dc.title | ON THE MINIMALITY OF POLYGON TRIANGULATION | en_US |
| dc.type | Article | en_US |