Quickhull: “a method of computing the convex hull of a finite set of points in n-dimensional space.” Invented in 1996.
It uses a divide-and-conquer method.
” Find the points with minimum and maximum x coordinates, as these will always be part of the convex hull.
Use the line formed by the two points to divide the set in two subsets of points, which will be processed recursively.
Determine the point, on one side of the line, with the maximum distance from the line. This point forms a triangle with those of the line.
The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
Repeat the previous two steps on the two lines formed by the triangle (not the initial line).
Keep on doing so on until no more points are left, the recursion has come to an end and the points selected constitute the convex hull. ”
invented in 1996 by C. Bradford Barber, David P. Dobkin, and Hannu Huhdanpaa