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  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.
ASJC Scopus subject areas
- Signal Processing
- Computer Vision and Pattern Recognition
- Artificial Intelligence