Quickhull
Quickhull is a method of computing the convex hull of a finite set of points in "n"-dimensional space. It uses a divide and conquer approach similar to that of quicksort, from which its name derives. Its worst case complexity for 2-dimensional and 3-dimensional space is considered to be formula_1, where formula_2 is the number of input points and formula_3 is the number of processed points. However, unlike quicksort, there is no obvious way to convert quickhull into a randomized algorithm. Nevertheless, there exist works from Smoothed Analysis which tell us that the 2-dimensional Quick hull algorithm  has expected runtime formula_4. Indeed, and related works show that the number of points on the convex hull of any randomly perturbed pointset with Gaussian noise is formula_5 from which it follows that Quick hull (and many other algorithms) can only takes time formula_6 on any set of perturbed points. N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa. It was an extension of Jonathan Scott Greenfield's 1990 planar Quickhull algorithm, although the 1996 authors did not know of his methods. Instead, Barber et al describes it as a deterministic variant  of Clarkson and Shor's 1989 algorithm. Algorithm. Under average circumstances the algorithm works quite well, but processing usually becomes slow in cases of high symmetry or points lying on the circumference of a circle. The algorithm can be broken down to the following steps: The problem is more complex in the higher-dimensional case, as the hull is built from many facets; the data structure needs to account for that and record the line/plane/hyperplane (ridge) shared by neighboring facets too. For "d" dimensions: Pseudocode for 2D set of points. Input = a set S of n points  A pseudocode specialized for the 3D case is available from Jordan Smith. It includes a similar "maximum point" strategy for choosing the starting hull. If these maximum points are degenerate, the whole point cloud is as well.