Qhull

The ideas behind quick-hull can be extended to three dimensions and higher. Several people have written programs to do this. One very successful program is called qhull. Other very good programs can be found at the Geometry Center's collection of geometric software. Click here to visit it.

Partitioning in quick-hull

To extend quick-hull to higher dimensions, we need to look more closely at the idea of partitioning. It occurs in two places:

1. At the beginning, when points are grouped into two sets: those above the chord, and those below it.
2. At each iteration, when points are partitioned into three sets: those inside the new triangle, and those outside the two edges.

Partitioning in Qhull

1. Those inside the hull. These points cannot contribute to the hull, so they are ignored in later processing.
2. Those outside. These points in turn are further partitioned, and each one is assigned to one of the facets of the hull. This partitioning is arbitrary, except that points must be above the facet with which they are associated.

Iteration

1. Choose a facet arbitrarily.
2. Examine the points associated with that facet, and pick the farthest one as a new vertex.
3. Extend the hull out to the new vertex. We do this as follows:
   1. Find the facets which are visible from the new vertex, and gather them into a set.
   2. Find the boundary of the visible set. This is the horizon, the boundary between the parts of the hull that are visible to the new vertex, and those that are invisible to it.
   3. From each part of the horizon (in three dimensions, from each edge of the horizon), extend the hull out to the new vertex.
   4. Remove the visible set.
4. The facet chosen in step 1 is now gone, and so are the facets on the visible set. The points that were associated with these facets must be:
   1. discarded (if they are now inside the new hull), or
   2. re-assigned to other facets.

Animation

All of this is hard to follow without a picture. Here's an animation of qhull. Click here for instructions. Unfortunately, it does not show the associations between facets and points (I was a bit lazy), but it does show how, at each iteration, the visible facets are removed, and the new pyramid of facets is added out to the new vertex.

Use the mouse to rotate the scene in case the interesting stuff is happening on the far side of the hull.

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