Chan's algorithm
In computational geometry, Chan's algorithm,[1] named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set
is the number of vertices of the output (the convex hull).
algorithm (Graham scan, for example) with Jarvis march (
This paradigm[2] has been independently developed by Frank Nielsen in his Ph.D.
[3] A single pass of the algorithm requires a parameter
, the number of vertices in the output convex hull, is not known at the start.
Multiple passes with increasing values of
The algorithm starts by arbitrarily partitioning the set of points
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
with the lowest y coordinate, which is guaranteed to be in the convex hull of
points (listed in a clockwise or counter-clockwise order), which allows to compute
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
For those points, one iteration of Jarvis's march is
Jarvis's march completes when the process has been repeated
times (because, in the way Jarvis march works, after at most
, we must have found the convex hull), hence the second phase takes
steps in the second phase, we interrupt the Jarvis's march as running it to the end would take too much time.
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
; each pass terminates (successfully or unsuccessfully) in
increases too slowly between passes, the number of iterations may be large; on the other hand, if it rises too quickly, the first
for which the algorithm terminates successfully may be much larger than
iterations are made, given that the algorithm terminates once we have with the logarithm taken in base
, and the total running time of the algorithm is To generalize this construction for the 3-dimensional case, an
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.
[1] 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,
Chan's paper contains several suggestions that may improve the practical performance of the algorithm, for example: Chan's paper contains some other problems whose known algorithms can be made optimal output sensitive using his technique, for example:
