This algorithm is called QUICK_HULL by Preparata & Shamos because of its similarity to the Hoare’s QUICK_SORT. This divide-and-conquer algorithm is based on the observation that we can discard most of the points in the given set as interior points and concentrate on remaining points. We accomplished this by partitioning the given set S of n points into two subsets, each of which will contain one of two polygonal chains whose concatenation gives the convex hull polygon.

The partition is determined by the line passing through two distinct extreme points: we will use the rightmost lowest and leftmost highest points r and l, which are guaranteed extreme and distinct by lemma?. The complete convex hull is composed of two hulls namely ‘upper hull’ which is above the extreme points and ‘lower hull’ which is below the extreme points. The algorithm finds these hulls by starting with extreme points (x, y), finds a third extreme point z strictly right of line(xy), discard all points inside the triangle(xyz), and runs recursively on line(xz) and line(zy). The key idea is point z which is furthest away from line(zy) must be on the hull. Therefore, we can discard all points on or in the triangle(xyz) except vertices of triangle. Repeat the same procedure on the set of points right of line(xz) and the set of points right of line(zy).

QUICKHULL (S, l, r)

if S={ } then return ()
    else if S={l, r} then return (l, r)      // a single convex hull edge
        else
            z = index of a point that is furthest (max distance) from xy.
            Let A be the set containing points strictly right of (x, z)
            Let B be the set containing points strictly right of (z, y)
            return {QUICKHULL (A, x, z) U (z) U QUICKHULL (B, z, y)}

Analysis

Finding the extremes require O(n) time. For the recursive function, it takes n steps to determine the extreme point z, but the cost of recursive calls depends on the sizes of set A and set B.

Best case    Consider the best possible case, when each partition is almost balanced. Then we have

T(n) = 2T(n/2) + O(n).

This is a familiar recurrence relation, whose solution is

T(n)=O(n log n).

Therefore O(n log n) is the best case, which would occur with randomly distributed points.

Worst case    The worst case occurs when each partition is an extremely unbalanced. In that case the recurrence relation is

T(n) = T(n - 1) + O(n)
    = T(n - 1) + cn

Repeated expansion shows this is O(n²). Therefore, in the worst case the QuickHull is quadratic.