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.