GrahamYao convex hull in the plane

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 Quicksort to sort coordinates. You can compare with another version using insertion sort.
(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.

• Detail toggles the vertex numbers and some of the edge weights.
• Animate toggles some animation of partial computation
• Update is the button you push when the input is ready; If comparing times, click twice because the first time may include loading or swapping time.
• Random generates 50 random points
• Clear All and Delete Last give minimalist editing.

Code by Jack Snoeyink, University of British Columbia Back to Jack's Computational Geometry Demo page.