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
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)