Quickhull convex hull in the plane

The divide & conquer algorithm that is the analogue of Quicksort for sorting. Quadratic worst case because the "pivot" is determined by geometry. Chan's modifications make this O(n log h) worst case!

• 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.