# Randomized convex hull

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.

• Perhaps this is better suited to cstheory. – Yuval Filmus May 21 '13 at 22:55
• Did you try to google it? – Yuval Filmus May 21 '13 at 23:02