A single pass of the algorithm requires a parameter which is between 0 and . Ideally, but, the number of vertices in the output convex hull, is not known at the start. Multiple passes with increasing values of are done which then terminates when. The algorithm starts by arbitrarily partitioning the set of points into subsets with at most points each; notice that. For each subset, it computes the convex hull,, using an algorithm, where is the number of points in the subset. As there are subsets of points each, this phase takes time. During the second phase, Jarvis's march is executed, making use of the precomputed convex hulls,. At each step in this Jarvis's march algorithm, we have a point in the convex hull, and need to find a point such that all other points of are to the right of the line, where the notation simply means that the next point, that is, isdetermined as a function of and. The convex hull of the set,, is known and contains at most points, which allows to compute in time by binary search. Hence, the computation of for all the subsets can be done in time. Then, we can determine using the same technique as normally used in Jarvis's march, but only considering the points instead of the whole set. For those points, one iteration of Jarvis's march is which is negligible compared to the computation for all subsets. Jarvis's march completes when the process has been repeated times, hence the second phase takes time, equivalent to time if is close to . By running the two phases described above, the convex hull of points is computed in time.
Choosing the parameter
If an arbitrary value is chosen for, it may happen that. In that case, after 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 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 in time. If 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, and produce a complexity.
Squaring Strategy
One possible strategy is to square the value of at each iteration, up to a maximum value of . Starting from a value of 2, at iteration, is chosen. In that case, 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. The time complexity remains.
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,, of a set of points,
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.
With the above idea, the dominant cost of algorithm lies in the pre-processing, i.e., the computation of the convex hulls of the groups. To reduce this cost, we may consider reusing hulls computed from the previous iteration and merging them as the group size is increased.
Extensions
Chan's paper contains some other problems whose known algorithms can be made optimal output sensitive using his technique, for example:
Computing the lower envelope of a set of line segments, which is defined as the lower boundary of the unbounded trapezoid of formed by the intersections.
Hershberger gave an algorithm which can be sped up to, where h is the number of edges in the envelope
Constructing output sensitive algorithms for higher dimensional convex hulls. With the use of grouping points and using efficient data structures, complexity can be achieved provided h is of polynomial order in.
