3D Convex Hull Construction

Randomized Incremental Algorithm

This algorithm was first described by K.L. Clarkson and P.W. Shor in 1989. I used the description found in Computational Geometry by de Berg, van Kreveld, Overmars, and Schwarzkopf as the basis for this implementation.

The O(n2) version of this algorithm is relatively easy to describe and understand. Given a set of n points in R3:

  1. Construct a tetrahedron by connecting the first four points of the input set.

    Fig 1: The initial tetrahedron

  2. For each remaining point p:

    1. Imagine that p is a small light bulb shining in a dark room. Determine the set of facets that this light bulb illuminates. We'll call this set of facets F, and we'll say that these facets are visible to p.

      Fig 2: The visible facets are drawn in white, and
      the horizon edges are outlined in dark black.
    2. Determine the set of horizon edges for point p. A horizon edge is an edge that runs along both a visible and non-visible facet. You can think of it as a line that separates what point p can see from what it can't see. The horizon edges form a connected loop around the visible facets.

    3. For each horizon edge, create a new triangular facet connecting the edge to point p. Point p is now part of the convex hull.

      Fig 3: The horizon is now connected to point p.
    4. Finally, discard all of the facets that were previously visible to point p.

Using a data structure called a conflict graph, the Clarkson-Shor version of this algorithm is able to construct the convex hull in O(n log n) expected time based on a random permutation of the input set. To understand how this works, we first need to examine the O(n2) version of the algorithm a little more closely.

Specifically, let's look at step 2a where we find a set of facets that is visible to the current point. The naive way to do this is to test every facet we've created so far. If the point is in front of the facet, then the facet is visible, and if the point is behind the facet, then the facet is not visible (we can use the facet's normal vector to determine which side of the facet is the front and which is the back).

A conflict graph is a bipartite graph with nodes representing points on one side and nodes representing facets on the other. If a point and a facet are connected by an arc, it means that the facet is visible to the point. When the algorithm adds a new point to the convex hull (step 2a), it can use the conflict graph to quickly determine the set of visible facets.

Fig 4: In a Conflict Graph, a facets is connected to a point if they are visible to each other.

The algorithm initializes the conflict graph after step 1 by testing each point against the four facets of the original tetrahedron. After each successive point is added to convex hull in step 2c, the new facets that were created must also be added to the conflict graph.

How can we efficiently update the conflict graph for each new facet? First, we know that any point that can see a new facet f can also see all three of the edges that form the boundary of f. One these edges also must be a horizon edge. Before we added f, there were two other facets that shared that same horizon edge. Let's call these two facets g and h. If a point could see that horizon edge, then it must also have been able to see either facet g or facet h. Therefore, to find the set of points visible to f, the algorithm only needs to consider the set of points that were visible to either g or h.

Fig 5: Facet f is being added to the convex hull.
Facets f, g and h all share the same horizon edge
(drawn with a dark black line).