Chapter 9 - Convex hulls in two and three dimensions

Summary

There are many algorithms that compute the convex hull of a set of points in two and three dimensions, and the present chapter does not claim to give a comprehensive survey. In fact, our goal is mainly to explore the possibilities offered by the divide-and-conquer method in two and three dimensions, and to expand on the incremental method in the case of a planar polygonal line.

In dimension 2, the divide-and-conquer method leads, like many other methods, to a convex hull algorithm that is optimal in the worst case. The main advantage of this method is that it also generalizes to three dimensions while still leading to an algorithm that is optimal in the worst case, which is not the case for the incremental method described in chapter 8. The performances of this divide-andconquer algorithm rely on the existence of a circular order on the edges incident to a given vertex. In dimensions higher than three, such an order does not exist, and the divide-and-conquer method is no longer efficient for computing convex hulls. The 2-dimensional divide-and-conquer algorithm is described in section 9.2, and generalized to dimension 3 in section 9.3. But before these descriptions, we must comment on the representation of polytopes in dimensions 2 and 3, and describe a data structure that explicitly provides the circular order of the edges or facets around a vertex of a 3-dimensional polytope.