Report Number: CS-TR-81-887
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