Quick-Hull

Here's an algorithm that deserves its name. It's a fast way to compute the convex hull of a set of points on the plane. It shares a few similarities with its namesake, quick-sort: The partitioning step does all the work. The basic idea is as follows:

  1. 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.
  2. Among the given points, find the one which is farthest from AB. Let's call this point C.
  3. The points inside the triangle ABC cannot be on the hull. Put them in set s0.
  4. Put the points which lie outside edge AC in set s1, and points outside edge BC in set s2.
Once the partitioning is done, we recursively invoke quick-hull on sets s1 and s2. The algorithm works fast on random sets of points because step 3 of the partition typically discards a large fraction of the points.

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.


*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***


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.


*** SORRY! You need a java-enabled browser to run this applet. Otherwise, you'll only see this text. ***


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