Chan's algorithm
Encyclopedia
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, in order to obtain an optimal O(n log h) time. Chan's algorithm is notable because it is much simpler than the ultimate planar convex hull algorithm, and it naturally extends to 3-dimensional space.
The second phase consists of executing Jarvis march
and using the precomputed convex hulls to speed up the execution. At each step in the Jarvis march algorithm, we have a point pi in the convex hull, and need to find a point pi+1 = f(pi,P) such that all other points of P are to the right of the line pi pi+1. If we know the convex hull of a set Q of m points, then we can compute f(pi,Q) in O(log m) time, by using binary search. We can compute f(pi,Q) for all the O(n/m) subsets Q in O(n/m log m) time. Then, we can determine f(pi,P) using the same technique as normally used in Jarvis March, but only considering the points that are f(pi,Q) for some subset Q. As the Jarvis march algorithm repeats this process O(h) times, the second phase also takes O(n log m) time, and if m=h, O(n log h) time.
By running the two phases described above, we can compute the convex hull of n points in O(n log h) time, assuming that we know the value of h. If we make m, we can abort the execution after m+1 steps, therefore spending only O(n log m) time (but not computing the convex hull). We can initially set m as a small constant (we use 2 for our analysis, but in practice numbers around 5 may work better), and increase the value of m until m>h, in which case we obtain the convex hull as a result.
If we increase the value of m too slowly, we may need to repeat the steps mentioned before too many times, and the execution time will be large. On the other hand, if we increase the value of m too quickly, we risk making m much larger than h, also increasing the execution time. Chan's algorithm squares the value of m at each iteration, and makes sure that m is never larger than n. In other words, at iteration t (starting at 0), we have
. The total running time of the algorithm is
To generalize this construction for the 3-dimensional case, an O(n log n) algorithm to compute the 3-dimensional convex hull should be used instead of Graham scan, and a 3-dimensional version of Jarvis march needs to be used. The time complexity remains O(n log h).
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
, Chan's algorithm, named after Timothy M. Chan
Timothy M. Chan
Timothy Moon-Yew Chan is Professor and University Research Chairin the David R. Cheriton School of Computer Science, University of Waterloo, Canada.He graduated with BA from Rice University in 1992, and completed his Ph.D...
, is an optimal output-sensitive algorithm
Output-sensitive algorithm
In computer science, an output-sensitive algorithm is an algorithm whose running time depends not only on the size of the input but also on the size of the output...
to compute the convex hull
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
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
Graham scan
The Graham scan is a method of computing the convex hull of a finite set of points in the plane with time complexity O. It is named after Ronald Graham, who published the original algorithm in 1972...
, for example) with Jarvis march, in order to obtain an optimal O(n log h) time. Chan's algorithm is notable because it is much simpler than the ultimate planar convex hull algorithm, and it naturally extends to 3-dimensional space.
Algorithm
Initially, we assume that the value of h is known and make a parameter m=h. This assumption is not realistic, but we remove it later. The algorithm starts by arbitrarily partitioning P into at most 1+n/m subsets Q with at most m points each. Then, it computes the convex hull of each subset Q using an O(n log n) algorithm. Note that, as there are O(n/m) subsets of O(m) points each, this phase takes O(n/m)O(m log m) = O(n log m) time.The second phase consists of executing Jarvis march
Gift wrapping algorithm
In computational geometry, the gift wrapping algorithm is an algorithm for computing the convex hull of a given set of points.-Planar case:In the two-dimensional case the algorithm is also known as Jarvis march, after R. A. Jarvis, who published it in 1973; it has O time complexity, where n is the...
and using the precomputed convex hulls to speed up the execution. At each step in the Jarvis march algorithm, we have a point pi in the convex hull, and need to find a point pi+1 = f(pi,P) such that all other points of P are to the right of the line pi pi+1. If we know the convex hull of a set Q of m points, then we can compute f(pi,Q) in O(log m) time, by using binary search. We can compute f(pi,Q) for all the O(n/m) subsets Q in O(n/m log m) time. Then, we can determine f(pi,P) using the same technique as normally used in Jarvis March, but only considering the points that are f(pi,Q) for some subset Q. As the Jarvis march algorithm repeats this process O(h) times, the second phase also takes O(n log m) time, and if m=h, O(n log h) time.
By running the two phases described above, we can compute the convex hull of n points in O(n log h) time, assuming that we know the value of h. If we make m
If we increase the value of m too slowly, we may need to repeat the steps mentioned before too many times, and the execution time will be large. On the other hand, if we increase the value of m too quickly, we risk making m much larger than h, also increasing the execution time. Chan's algorithm squares the value of m at each iteration, and makes sure that m is never larger than n. In other words, at iteration t (starting at 0), we have
. The total running time of the algorithm isTo generalize this construction for the 3-dimensional case, an O(n log n) algorithm to compute the 3-dimensional convex hull should be used instead of Graham scan, and a 3-dimensional version of Jarvis march needs to be used. The time complexity remains O(n log h).
Implementation
Chan's paper contains several suggestions that may improve the practical performance of the algorithm, for example:- When computing the convex hulls of the subsets, eliminate the points that are not in the convex hull from consideration in subsequent executions.
- The convex hulls of larger point sets can be obtained by merging previously calculated convex hulls, instead of recomputing from scratch.