Convex Hull
Problem Description
The Convex Hull of the polygon is the minimal convex set wrapping our polygon.
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) 