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]
The 2-dimensional algorithm can be broken down into the following steps:[2]
The problem is more complex in the higher-dimensional case, as the hull is built from many facets; the data structure needs to account for that and record the line/plane/hyperplane (ridge) shared by neighboring facets too. For d dimensions:[1]
Input = a set S of n points Assume that there are at least 2 points in the input set S of points function QuickHull(S) is // Find convex hull from the set S of n points Convex Hull := {} Find left and right most points, say A & B, and add A & B to convex hull Segment AB divides the remaining (n − 2) points into 2 groups S1 and S2 where S1 are points in S that are on the right side of the oriented line from A to B, and S2 are points in S that are on the right side of the oriented line from B to A FindHull(S1, A, B) FindHull(S2, B, A) Output := Convex Hull end function function FindHull(Sk, P, Q) is // Find points on convex hull from the set Sk of points // that are on the right side of the oriented line from P to Q if Sk has no point then return From the given set of points in Sk, find farthest point, say C, from segment PQ Add point C to convex hull at the location between P and Q Three points P, Q, and C partition the remaining points of Sk into 3 subsets: S0, S1, and S2 where S0 are points inside triangle PCQ, S1 are points on the right side of the oriented line from P to C, and S2 are points on the right side of the oriented line from C to Q. FindHull(S1, P, C) FindHull(S2, C, Q) end function
A pseudocode specialized for the 3D case is available from Jordan Smith. It includes a similar "maximum point" strategy for choosing the starting hull. If these maximum points are degenerate, the whole point cloud is as well.[3]