On the minimality of polygon triangulation

Chiuyuan Chen*, Ruei Chuan Chang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

6 Scopus citations

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+2 w -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.

Original languageEnglish
Pages (from-to)570-582
Number of pages13
JournalBIT
Volume30
Issue number4
DOIs
StatePublished - 1 Dec 1990

Keywords

  • G.1.6
  • I.1.2
  • I.3.5

Fingerprint Dive into the research topics of 'On the minimality of polygon triangulation'. Together they form a unique fingerprint.

Cite this