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 , where is the number of input points and 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 . Indeed, and related works show that the number of points on the convex hull of any randomly perturbed pointset with Gaussian noise is from which it follows that Quick hull (and many other algorithms) can take only time 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. (Wikipedia).