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!

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