The O(n^{2}) version of this algorithm is relatively easy to describe and understand. Given a set of n points in R^{3}:
Fig 2: The visible facets are drawn in white, and the horizon edges are outlined in dark black. |
Fig 3: The horizon is now connected 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(n^{2}) 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). |