Randomized convex hull

Question

I've been recently studying Monte-Carlo and other randomized methods for a lot of applications, and one that popped into my mind was making an (approximate) convex hull by examining random points, and try to get them inside the convex hull. I would like to know if there are algorithms for convex hulls that can improve the $O(n \log n)$ bound of comparison based algorithms, and the $O(n\cdot h)$ bound for Jarvis march and related to $O(n)$, either by building an approximate convex hull in $O(n)$ (with or without some approximation criteria) or by building an exact convex hull in expected linear time.

Answer 1

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.