Quickhull

Quickhull is a method of computing the <a href="/facts/Convex_hull/D4Id3JDS">convex hull</a> of a finite set of points in n-dimensional space. It uses a <a href="/facts/Divide_and_conquer_algorithm/pC1X7Ws7">divide and conquer</a> approach similar to that of <a href="/facts/Quicksort/1BeqhLAH">quicksort</a>, from which its name derives. Its worst case time complexity for 2-dimensional and 3-dimensional space is 
 
 
 
 O
 (
 
 n
 
 2
 
 
 )
 
 
 {\displaystyle O(n^{2})}
 
, but when the input precision is restricted to 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 bits, its worst case time complexity is conjectured to be 
 
 
 
 O
 (
 n
 log
 ⁡
 r
 )
 
 
 {\displaystyle O(n\log r)}
 
, where 
 
 
 
 n
 
 
 {\displaystyle n}
 
 is the number of input points and 
 
 
 
 r
 
 
 {\displaystyle r}
 
 is the number of processed points (up to 
 
 
 
 n
 
 
 {\displaystyle n}
 
). 
N-dimensional Quickhull was invented in 1996 by C. Bradford Barber, <a href="/facts/David_P._Dobkin/gAKUXmsz">David P. Dobkin</a>, 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. describe it as a deterministic variant of Clarkson and Shor's 1989 algorithm.

Quickhull open-in-new

Quickhull