Quickhull

Quickhull is an algorithm for computing the convex hull of a finite set of points. It is a divide-and-conquer method commonly used in computational geometry and can be applied in two dimensions as well as generalized to higher dimensions. The name reflects its relationship to the QuickSort algorithm in its recursive splitting approach.

In two dimensions, Quickhull typically starts by identifying the leftmost and rightmost points; these points must lie on the hull and define an initial line segment. All other points are divided into two groups based on which side of the line they lie. The algorithm processes each side independently: for a line segment AB, it finds the point C on the chosen side that is farthest from AB. Point C is added to the hull, and the remaining points are partitioned relative to lines AC and CB. The procedure recurses on the two new subsets. Points that lie inside the triangle ABC cannot be on the hull and are discarded. The recursion terminates when no points remain on a given side.

Complexity and behavior: Quickhull runs in O(n log n) on average for two-dimensional inputs, but the worst-case time can degrade to O(n^2) depending on the distribution of points. The algorithm is data-dependent and tends to perform well in practice for many point sets.

Extensions and notes: Quickhull can be generalized to higher dimensions by replacing lines with hyperplanes and triangles with higher-dimensional simplices. It yields the hull’s vertices and facets through a recursive peeling process and is commonly used in applications such as computer graphics, geographic information systems, and collision detection.