Institution: Stanford University, Department of Computer Science

Title: Finding the convex hull of a simple polygon

Author: Graham, Ronald L.

Author: Yao, Frances

Date: November 1981

Abstract: It is well known that the convex hull of a set of n points in the (Euclidean) plane can be found by an algorithm having worst-case complexity O(n log n). In this note we give a short linear algorithm for finding the convex hull in the case that the (ordered) set of points from the vertices of a simple (i.e., non-self-intersecting) polygon.

http://i.stanford.edu/pub/cstr/reports/cs/tr/81/887/CS-TR-81-887.pdf