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)

ifS={ } then return ()

else ifS={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)}

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^{2}). Therefore, in the worst case the QuickHull is
quadratic.