Convex Hull

From Algorithm Wiki
Revision as of 15:12, 20 September 2021 by Yashsherry (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
Exp/Factorial
Polynomial > 3
Cubic [Brute Force (1935)]
Quadratic
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)

Linear
logn Miller; Stout 1988 (1988)