The Graham scan triangulates simple polygons

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(n²), it is easy to implement and is therefore of practical interest.