Convex Hull
Jump to navigation
Jump to search
Problem Description
The Convex Hull is the line completely enclosing a set of points in a plane so that there are no concavities in the line. More formally, we can describe it as the smallest convex polygon which encloses a set of points such that each point in the set lies within the polygon or on its perimeter.
Bounds Chart
Step Chart
Improvement Table
| Complexity Classes | Algorithm Paper Links | Lower Bounds Paper Links |
|---|---|---|
| Exp/Factorial | ||
| Polynomial > 3 | ||
| Cubic | [Brute Force (1935)] | |
| Quadratic | ||
| nlogn | Graham (1972)
W. Eddy Quickhull; 1977 (1977) Incremental convex hull algorithm; Michael Kallay (1984) |
|
| Linear | ||
| logn | Miller; Stout 1988 (1988) |