Efficient triangulation of simple polygons

Research output: Contribution to journalArticle

Abstract

This paper considers the topic of efficiently traingulating a simple polygon with emphasis on practical and easy-to-implement algorithms. It also describes a new adaptive algorithm for triangulating a simple n-sided polygon. The algorithm runs in time O(n(1+to)) with t0<n. The quantity t0 measures the shape-complexity of the triangulation delivered by the algorithm. More precisely t0 is the number of obtained triangles contained in the triangulation that share zero edges with the input polygon and is, furthermore, related to the shape-complexity of the input polygon. Although the worst-case complexity of the algorithm is O(n2), for several classes of polygons it runs in linear time. The practical advantages of the algorithm are that it is simple and does not require sorting or the use of balanced tree structures. On the theoretical side, it is of interest because it is the first polygon triangulation algorithm where the computational complexity is a function of the output complexity. As a side benefit, we introduce a new measure of the complexity of a polygon triangulation that should find application in other contexts as well.

Original languageEnglish (US)
Pages (from-to)280-295
Number of pages16
JournalThe Visual Computer
Volume7
Issue number5-6
DOIs
StatePublished - Sep 1991

Keywords

  • Algorithm
  • Computational geometry
  • Geometric Complexity
  • Polygon
  • Triangulation

ASJC Scopus subject areas

  • Software
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Efficient triangulation of simple polygons'. Together they form a unique fingerprint.

  • Cite this