Randomized convex hull
Two linear time approximation algorithms in the two-dimensional case are due to Bentely, Preparata and Faust and Stojmenović and Soisalon-Soininen.

A fast exact algorithm which works in expected linear time is due to Bentley, Clarkson and Levine. The paper is quite old, so maybe there are newer developments.