Chan's Algorithm

Chan's algorithm computes the convex hull of a set of points in O(n log h) time, where h is the number of points on the hull, combining the divide and conquer efficiency of algorithms like Quickhull with the output sensitivity of Jarvis march. It works by partitioning the points into small groups, computing each group's hull with a simple O(n log n) method, and merging the results using a gift wrapping style step whose group size is doubled across repeated guesses until the true hull size is found. Timothy Chan published the algorithm in 1996, and it is regarded as asymptotically optimal for the convex hull problem.