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.