- it is recursive.
- each recursive step partitions data into several groups.

- We are given a some points, and line segment
*AB*which we know is a chord of the convex hull (IE, it's endpoints are known to be on the convex hull). A good chord to start the algorithm goes from the leftmost to the rightmost point in the set. - Among the given points, find the one which
is farthest from
*AB*. Let's call this point*C*. - The points inside the triangle
*ABC*cannot be on the hull. Put them in set*s0*. - Put the points which lie outside edge
*AC*in set*s1*, and points outside edge*BC*in set*s2*.

Here's a demonstration of quick-hull, on a set of 50 random points.
At each step, points in *s0* are yellow, points in *s1*
blue, and points in *s2* black. Click on "Run" to start the demo.

Now, see what happens with 50 points arranged in a circle. As you can see,
no points are discarded (*s0* is always empty, and there are no
yellow points), so the algorithm runs more slowly. For this particular
example, Graham's scan may be more efficient.

Alejo Hausner, CS Department, Princeton University Last modified: Mon Jun 9 15:52:25 1997