Chan's Algorithm
Chan's algorithm is an optimal output-sensitive computational geometry algorithm that computes the convex hull of n points in two or three dimensions in O(n log h) time.
Chan's algorithm, introduced by Canadian computer scientist Timothy M. Chan in 1996, is an output-sensitive computational geometry algorithm that computes the convex hull of a set P of n points in two-dimensional or three-dimensional Euclidean space in O(n log h) time, where h is the number of vertices on the resulting convex hull. Achieving the information-theoretic lower bound for planar convex-hull construction while remaining conceptually simpler than earlier optimal methods (Kirkpatrick & Seidel, 1986), Chan's algorithm elegantly combines Graham scan with Jarvis march via an iterative doubling-parameter search.
Output-Sensitive Lower Bounds and Prior Trade-offs
Classical planar convex-hull algorithms exhibit complementary strengths depending on hull size h:
- Graham scan (Graham, 1972) sorts all n input points by polar angle or x-coordinate and constructs the hull in O(n log n) time regardless of h.
- Jarvis march (gift wrapping) steps from one hull vertex to the next by scanning remaining points, taking O(nh) time—faster than Graham scan when h = o(log n), yet quadratic when h = Θ(n).
In 1986, Kirkpatrick and Seidel proved an Ω(n log h) lower bound in the algebraic decision-tree model and presented a divide-and-conquer "ultimate" planar convex-hull algorithm matching that bound, though its prune-and-search median-finding steps carry high implementation complexity. Chan (1996) demonstrated how to match O(n log h) using standard, practical primitives.
Algorithmic Mechanics: Partition, Sub-Hull, and Gift Wrap
Fixed-Budget Phase (m Guess)
Suppose an upper bound m ≥ h on the true number of hull vertices were known in advance. Chan's algorithm executes three steps:
- Partition: Split the n input points arbitrarily into r = ⌈n / m⌉ disjoint subsets P₁, P₂, ..., Pᵣ, each containing at most m points.
- Sub-Hull Construction: Compute the convex hull Hᵢ of each subset Pᵢ independently using Graham scan in O(m log m) time per group, totaling O((n/m) · m log m) = O(n log m) time across all subsets.
- Accelerated Jarvis March: Starting from the lexicographically lowest point p₀ (guaranteed to lie on the global hull), advance vertex by vertex for at most m steps. At each current hull vertex pₖ, find the supporting tangent to every sub-hull Hᵢ in O(log m) time via binary search over *Hᵢ*'s cyclic vertex array, then select the global next vertex maximizing the exterior turn angle among the r candidate tangents. Each Jarvis step takes O((n/m) log m) time, so m steps cost O(n log m) total.
If the Jarvis march returns to p₀ within m steps, the complete global convex hull has been found; otherwise, m < h and the phase aborts early.
Exponential Squaring Search for m
Because h is unknown beforehand, Chan's algorithm runs sequential phases with a rapidly growing guess m = min(n, 2^(2^t)) for t = 1, 2, 3, ... until a phase succeeds. Since log(2^(2^t)) = 2^t, the summed cost across all phases up to the first t satisfying 2^(2^t) ≥ h forms a geometric series bounded by O(n · 2^t) = O(n log h), preserving optimal asymptotic complexity without knowing h in advance.
Three-Dimensional Generalization and Practical Impact
In three dimensions, Chan's same partition-and-wrap strategy extends to O(n log h) time by computing 3D sub-hulls with Preparata–Hong O(m log m) divide-and-conquer and querying extreme tangents over Dobkin–Kirkpatrick hierarchies in O(log m) time per sub-hull. In applied geometric computing, robotics collision-detection, and geographic information systems (GIS), Chan's algorithm is particularly valuable when large-scale point clouds (such as LiDAR terrain scans) enclose relatively simple outer boundaries (h ≪ n), delivering substantial speedups over full O(n log n) sorting while maintaining clean, modular sub-routines.
Implementation Trade-Offs and Practical Considerations
Although Chan's algorithm achieves asymptotic optimality in the comparison-based model, its constant factors depend on binary-search tangent queries across r = ⌈n / m⌉ cyclic polygon arrays. When h is moderately large relative to n, the overhead of constructing multiple sub-hulls and repeating doubling phases can make a single-pass Graham scan or Andrew's monotone chain competitive in wall-clock runtime. Consequently, high-performance geometry libraries often pair Chan's algorithm with a fast initial Akl–Toussaint heuristic—discarding points properly inside the quadrilateral formed by outer x and y coordinates—before launching sub-hull partitioning, capturing both linear-time pruning on dense point clouds and optimal O(n log h) worst-case guarantees across two- and three-dimensional spatial datasets. Together with Kirkpatrick–Seidel prune-and-search, Chan's method stands as a foundational result in output-sensitive computational geometry, illustrating how simple sub-algorithms can be orchestrated to match tight information-theoretic lower bounds for geometric hull construction in planar and spatial applications.
References
- Chan, T. M. (1996). Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4), 361–368. https://doi.org/10.1007/BF02712873
- Kirkpatrick, D. G., & Seidel, R. (1986). The ultimate planar convex hull algorithm? SIAM Journal on Computing, 15(1), 287–299. https://doi.org/10.1137/0215021
- Graham, R. L. (1972). An efficient algorithm for determining the convex hull of a finite planar set. Information Processing Letters, 1(4), 132–133. https://doi.org/10.1016/0020-0190(72)90045-290045-2)