Chan's algorithm
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 formula_1 of formula_2 points, in 2- or 3-dimensional space. The algorithm takes formula_3 time, where formula_4 is the number of vertices of the output (the convex hull). In the planar case, the algorithm combines an formula_5 algorithm (Graham scan, for example) with Jarvis march (formula_6), in order to obtain an optimal formula_3 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 formula_8 which is between 0 and formula_2 (number of points of our set formula_1). Ideally, formula_11 but formula_4, the number of vertices in the output convex hull, is not known at the start. Multiple passes with increasing values of formula_8 are done which then terminates when formula_14(see below on choosing parameter formula_8). The algorithm starts by arbitrarily partitioning the set of points formula_1 into formula_17 subsets formula_18 with at most formula_8  points each; notice that formula_20. For each subset formula_21, it computes the convex hull, formula_22, using an formula_23 algorithm (for example, Graham scan), where formula_24 is the number of points in the subset. As there are formula_25 subsets of formula_26 points each, this phase takes formula_27 time. During the second phase, Jarvis's march is executed, making use of the precomputed (mini) convex hulls, formula_28. At each step in this Jarvis's march algorithm, we have a point formula_29 in the convex hull (at the beginning, formula_29 may be the point in formula_1 with the lowest y coordinate, which is  guaranteed to be in the convex hull of formula_1), and need to find a point formula_33 such that all other points of formula_1 are to the right of the line formula_35, where the notation formula_33 simply means that the next point, that is formula_37, is determined as a function of formula_29 and formula_1. The convex hull of the set formula_21, formula_22, is known and contains at most formula_8 points (listed in a clockwise or counter-clockwise order), which allows to compute formula_43 in formula_44 time by binary search. Hence, the computation of formula_43 for all the formula_25 subsets can be  done in formula_47 time. Then, we can determine formula_48 using the same technique as normally used in Jarvis's march, but only considering the points formula_49 (i.e. the points in the mini convex hulls) instead of the whole set formula_1. For those points, one iteration of Jarvis's march is formula_51 which is negligible compared to the computation for all subsets. Jarvis's march completes when the process has been repeated formula_52 times (because, in the way Jarvis march works, after at most formula_4 iterations of its outermost loop, where formula_4 is the number of points in the convex hull  of formula_1, we must have found the convex hull), hence the second phase takes formula_56 time, equivalent to formula_3 time if formula_8 is close to formula_4 (see below the description of a strategy to choose formula_8 such that this is the case). By running the two phases described above, the convex hull of formula_2 points is computed in formula_3 time. Choosing the parameter formula_63. If an arbitrary value is chosen for formula_8, it may happen that formula_65. In that case, after formula_8 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 formula_67 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 formula_8; each pass terminates (successfully or unsuccessfully) in formula_67 time. If formula_8 increases too slowly between passes, the number of iterations may be large; on the other hand, if it rises too quickly, the first formula_8 for which the algorithm terminates successfully may be much larger than formula_4, and produce a complexity formula_73. Squaring Strategy. One possible strategy is to "square" the value  of formula_8 at each iteration, up to a maximum value of formula_2 (corresponding to a partition in singleton sets). Starting from a value of 2, at iteration formula_76, formula_77 is chosen. In that case, formula_78 iterations are made, given that the algorithm terminates once we have with the logarithm taken in base formula_80, and the total running time of the algorithm is In three dimensions. To generalize this construction for the 3-dimensional case, an formula_5 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 formula_3. 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, formula_84, of a set of points, formula_1. 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