Chan's algorithm

Chan's algorithm is an optimal output-sensitive algorithm to compute the convex hull of a set P of points in 2 or 3 dimensional space. We denote the number of points in the input by n, and the number of points in the output (the convex hull) by h. In the planar case, the algorithm combines an O(n log n) algorithm like Graham scan with Jarvis march, in order to obtain an optimal O(n log h) time.

First, we assume that the value of h is known. This assumption is not realistic, but we remove this assumption later. The algorithm starts by arbitrarily partitioning P into at most 1+n/h subsets with at most h points each. Then, it computes the convex hull of each subset using an O(n log n) algorithm. Note that, as there are O(n/h) sets of O(h) size, this phase takes O(n log h) time.