Quick-Hull: A quick-sort like algorithm for convex hull

Visualization:

The algorithm:

1. Find the points with minimum and maximum x coordinates. These will always be part of the convex hull.
2. The line formed by these points divide the remaining points into two subsets, which will be processed recursively.
3. Determine the point, on one side of the line, with the maximum distance from the line. This point will also be part of the convex hull. The two points found before along with this one form a triangle.
4. The points lying inside of that triangle cannot be part of the convex hull and can therefore be ignored in the next steps.
5. Repeat the previous two steps on the two lines formed by the triangle (not the initial line).
6. Stop when no more points are left.

Run-time:

The algorithm has a worst case run-time of O(n^2) and an average case run-time of O(n log n). However, note that it is possible for people to design data for which this algorithm will take O(n^2) time. For example, the algorithm has a bad run time when the points are located on the circumference of a circle.

Source: Wikipedia.