Convex hull algorithms

Summary

Convex hull algorithms take a finite set of $n$ points in $\R^d$ and compute its convex hull. The output is usually the list of its vertices or of its facets. In the plane, Graham scan and other methods run in $O(n \log n)$ time. Gift wrapping runs in $O(n h)$ time, where $h$ is the number of hull vertices. Chan's algorithm combines both ideas and runs in $O(n \log h)$ time. Since sorting reduces to the planar convex hull problem, $\Omega(n \log n)$ operations are needed in the worst case in the algebraic decision tree model. These algorithms are a basic building block of computational geometry.