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:
- it is recursive.
- each recursive step partitions data into several groups.
The partitioning step does all the work. The basic idea is as follows:
- 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.
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.
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