page_title: Quickhull
hierarchical_section_title: Quickhull
caption_attribution_description: English: This animation depicts the QuickHull algorithm.
context_page_description: 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. Thus, its average time complexity cannot be easily calculated.
  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.
context_section_description: 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. Thus, its average time complexity cannot be easily calculated.
  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.
caption: This animation depicts the quickhull algorithm.