The Graham scan triangulates simple polygons

Xianshu Kong, Hazel Everett, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review

Abstract

The Graham scan is a fundamental backtracking technique in computational geometry which was originally designed to compute the convex hull of a set of point in the plane [9] and has since found application in several different contexts. In this note we show how to use the Graham scan to triangulate a simple polygon. The resulting algorithm triangulates an n-vertex polygon P in O(kn) time where k -1 is the number of concave vertices in P. Although the worst case running time of the algorithm is O(n2), it is easy to implement and is therefore of practical interest.

Original languageEnglish (US)
Pages (from-to)713-716
Number of pages4
JournalPattern Recognition Letters
Volume11
Issue number11
DOIs
StatePublished - Nov 1990

ASJC Scopus subject areas

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

Fingerprint Dive into the research topics of 'The Graham scan triangulates simple polygons'. Together they form a unique fingerprint.

Cite this