Convex Hull

From Algorithm Wiki
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

Convex HullBoundsChart.png

Step Chart

Convex HullStepChart.png

Improvement Table

Complexity Classes Algorithm Paper Links Lower Bounds Paper Links
Polynomial > 3
Cubic [Brute Force (1935)]
nlogn Graham (1972)

W. Eddy Quickhull; 1977 (1977)

Preparata and Hong (1977)

Andrew's algorithm (1979)

Incremental convex hull algorithm; Michael Kallay (1984)

The ultimate planar convex hull algorithm (1986)

Chan's algorithm (1996)

logn Miller; Stout 1988 (1988)