On a convex hull algorithm for polygons and its application to triangulation problems

Godfried T. Toussaint, David Avis

Research output: Contribution to journalArticlepeer-review

Abstract

A frequently used algorithm for finding the convex hull of a simple polygon in linear running time has been recently shown to fail in some cases. Due to its simplicity the algorithm is, nevertheless, attractive. In this paper it is shown that the algorithm does in fact work for a family of simple polygons known as weakly externally visible polygons. Some application areas where such polygons occur are briefly discussed. In addition, it is shown that with a trivial modification the algorithm can be used to internally and externally triangulate certain classes of polygons in 0(n) time.

Original languageEnglish (US)
Pages (from-to)23-29
Number of pages7
JournalPattern Recognition
Volume15
Issue number1
DOIs
StatePublished - 1982

Keywords

  • Algorithm
  • Computational complexity
  • Computational geometry
  • Convex hull
  • Image processing
  • Pattern recognition
  • Simple polygon
  • Triangulation Polygon decomposition
  • Weakly externally visible polygon

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Artificial Intelligence

Fingerprint

Dive into the research topics of 'On a convex hull algorithm for polygons and its application to triangulation problems'. Together they form a unique fingerprint.

Cite this