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.
- 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 orange, points in
s1 green, and points in s2 blue. Click on "Init" to
run the program, then use the arrow buttons to play the events.
More detailed instructions are also
available.
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 orange points), so the algorithm runs more slowly. For
this particular example, Graham's scan may
be more efficient.
Finally, we can compare the algorithm's behavior on the two kinds
of inputs, with a side-by-side algorithm race:
Here is the java source code for
quick-hull.
Alejo Hausner, CS Department, Princeton University
Last modified: Thu Feb 25 17:21:22 EST 1999