Graham and Yao's algorithm maintains the convex hull incrementally in
two stacks (or a double ended queue) as
points are added in order of sorted x-coordinates. In this version we
use insertion sort to sort coordinates.
You can compare with another version using
Quicksort.
(Or go on to compare with Quickhull.)
Linear time after sorting; see R. L. Graham and F. F. Yao, "Finding the convex hull of a simple polygon," J. Algorithms, 4, 1983, p. 324--331.
Code by Jack Snoeyink, University of British Columbia Back to Jack's Computational Geometry Demo page.