Randomized quickhull
This paper contains a simple, randomized algorithm for constructing the convex hull of a set ofn points in the plane with expected running timeO(nlogh) whereh is the number of points on the convex hull.
Algorithmica