← Wiki Index / Computation & Algorithms / Chan's Algorithm
💻 Computation & Algorithms

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:

  1. Partition: Split the n input points arbitrarily into r = ⌈n / m⌉ disjoint subsets P₁, P₂, ..., Pᵣ, each containing at most m points.
  2. 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.
  3. 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

  1. 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
  2. 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
  3. 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)
🧬 Support Open Science
Explore interactive science games on LowKey Games or browse scientific apparel & accessories in the CRV Science Shop.
💡 Spot an inaccuracy or have primary literature to expand this article?
Submit a citation or revision note using your shared CRV Science / LowKey Games profile ID.
Suggest Revision