Idea
Take leftmost + rightmost points. They're on hull. Split remaining above/below. Find point farthest from line → on hull. Recurse on two subsets.
Advertisement
Complexity
Expected O(N log N). Worst O(N²) for adversarial input (all points on hull).
Advertisement
Higher dimensions
Generalizes to 3D+ (qhull). Useful for computing convex hulls of point clouds in ML/graphics.