Quickhull
From Wikipedia, the free encyclopedia
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 time complexity for 2-dimensional and 3-dimensional space is , but when the input precision is restricted to bits, its worst case time complexity is conjectured to be , where is the number of input points and is the number of processed points (up to ).[1]
N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa.[1] It was an extension of Jonathan Scott Greenfield's 1990 planar Quickhull algorithm, although the 1996 authors did not know of his methods.[2] Instead, Barber et al. describe it as a deterministic variant of Clarkson and Shor's 1989 algorithm.[1]