The Graham scan triangulates simple polygons

Xianshu Kong, Hazel Everett, Godfried Toussaint

Research output: Contribution to journalArticlepeer-review


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
Issue number11
StatePublished - Nov 1990

ASJC Scopus subject areas

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


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

Cite this