In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space. The algorithm takes O(n \log h) time, where h is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an O(n \log n) algorithm (Graham scan, for example) with Jarvis march (O(nh)), in order to obtain an optimal O(n \log h) time. Chan's algorithm is notable because it is much simpler than the Kirkpatrick–Seidel algorithm, and it naturally extends to 3-dimensional space. This paradigm has been independently developed by Frank Nielsen in his Ph.D. thesis.

Algorithm

Overview

A single pass of the algorithm requires a parameter m which is between 0 and n (number of points of our set P). Ideally, m = h but h, the number of vertices in the output convex hull, is not known at the start. Multiple passes with increasing values of m are done which then terminates when m \geq h(see below on choosing parameter m). The algorithm starts by arbitrarily partitioning the set of points P into subsets with at most m points each; notice that K=O(n/m). For each subset Q_k, it computes the convex hull, C_k, using an O(p \log p) algorithm (for example, Graham scan), where p is the number of points in the subset. As there are K subsets of O(m) points each, this phase takes time. During the second phase, Jarvis's march is executed, making use of the precomputed (mini) convex hulls,. At each step in this Jarvis's march algorithm, we have a point p_{i} in the convex hull (at the beginning, p_{i} may be the point in P with the lowest y coordinate, which is guaranteed to be in the convex hull of P), and need to find a point such that all other points of P are to the right of the line, where the notation simply means that the next point, that is p_{i+1}, is determined as a function of p_{i} and P. The convex hull of the set Q_k, C_k, is known and contains at most m points (listed in a clockwise or counter-clockwise order), which allows to compute in O(\log m) time by binary search. Hence, the computation of for all the K subsets can be done in O(K \log m) time. Then, we can determine f(p_{i},P) using the same technique as normally used in Jarvis's march, but only considering the points (i.e. the points in the mini convex hulls) instead of the whole set P. For those points, one iteration of Jarvis's march is O(K) which is negligible compared to the computation for all subsets. Jarvis's march completes when the process has been repeated O(h) times (because, in the way Jarvis march works, after at most h iterations of its outermost loop, where h is the number of points in the convex hull of P, we must have found the convex hull), hence the second phase takes time, equivalent to O(n \log h) time if m is close to h (see below the description of a strategy to choose m such that this is the case). By running the two phases described above, the convex hull of n points is computed in O(n \log h) time.

Choosing the parameter

m If an arbitrary value is chosen for m, it may happen that m<h. In that case, after m steps in the second phase, we interrupt the Jarvis's march as running it to the end would take too much time. At that moment, a O(n \log m) time will have been spent, and the convex hull will not have been calculated. The idea is to make multiple passes of the algorithm with increasing values of m; each pass terminates (successfully or unsuccessfully) in O(n \log m) time. If m increases too slowly between passes, the number of iterations may be large; on the other hand, if it rises too quickly, the first m for which the algorithm terminates successfully may be much larger than h, and produce a complexity.

Squaring Strategy

One possible strategy is to square the value of m at each iteration, up to a maximum value of n (corresponding to a partition in singleton sets). Starting from a value of 2, at iteration t, is chosen. In that case, iterations are made, given that the algorithm terminates once we have with the logarithm taken in base 2, and the total running time of the algorithm is

In three dimensions

To generalize this construction for the 3-dimensional case, an O(n \log n) algorithm to compute the 3-dimensional convex hull by Preparata and Hong should be used instead of Graham scan, and a 3-dimensional version of Jarvis's march needs to be used. The time complexity remains O(n \log h).

Pseudocode

In the following pseudocode, text between parentheses and in italic are comments. To fully understand the following pseudocode, it is recommended that the reader is already familiar with Graham scan and Jarvis march algorithms to compute the convex hull, C, of a set of points, P.

Implementation

Chan's paper contains several suggestions that may improve the practical performance of the algorithm, for example:

Extensions

Chan's paper contains some other problems whose known algorithms can be made optimal output sensitive using his technique, for example: