Convex Hull

From Algorithm Wiki
Jump to navigation Jump to search

Problem Description

The Convex Hull of the polygon is the minimal convex set wrapping our polygon.

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)