Convex Hull

  

 

Input description: A set S of n points in d-dimensional space.

Problem description: Find the smallest convex polygon containing all the points of S.

Discussion: Finding the convex hull of a set of points is the most elementary interesting problem in computational geometry, just as minimum spanning tree is the most elementary interesting problem in graph algorithms. It arises because the hull quickly captures a rough idea of the shape or extent of a data set.  

Convex hull also serves as a first preprocessing step to many, if not most, geometric algorithms. For example, consider the problem of finding the diameter of a set of points, which is the pair of points a maximum distance apart.   The diameter will always be the distance between two points on the convex hull. The algorithm for computing diameter proceeds by first constructing the convex hull, then for each hull vertex finding which other hull vertex is farthest away from it. This so-called ``rotating-calipers'' method can be used to move efficiently from one hull vertex to another.  

There are almost as many convex hull algorithms as there are sorting algorithms. Answer the following questions to help choose between them:

• How many dimensions are you working with? - Convex hulls in two and even three dimensions are fairly easy to work with. However, as the dimension of a space increases, certain assumptions that were valid in lower dimensions break down. For example, any n-vertex polygon in two dimensions has exactly n edges. However, the relationship between the numbers of faces and vertices is more complicated even in three dimensions. A cube has 8 vertices and 6 faces, while an octahedron has 8 faces and 6 vertices. This has implications for data structures that represent hulls - are you just looking for the hull points or do you need the defining polyhedron? The need to find convex hulls in high-dimensional spaces arises in many applications, so be aware of such complications if your problem takes you there.   

  Gift-wrapping is the basic algorithm for constructing higher-dimensional convex hulls. Observe that a three-dimensional convex polyhedron is composed of two-dimensional faces, or facets, which are connected by one-dimensional lines, or edges.   Each edge joins exactly two facets together. Gift-wrapping starts by finding an initial facet associated with the lowest vertex and then conducting a breadth-first search from this facet to discover new, additional facets. Each edge e defining the boundary of a facet must be shared with one other facet, so by running through each of the n points we can identify which point defines the next facet with e. Essentially, we ``wrap'' the points one facet at a time by bending the wrapping paper around an edge until it hits the first point.

  The key to efficiency is making sure that each edge is explored only once. Implemented properly in d dimensions, gift-wrapping takes , where is the number of facets and is the number of edges in the convex hull. Thus gift-wrapping can be very efficient when there is only a constant number of facets on the hull. However, this can be as bad as when the convex hull is very complex.

  Better convex hull algorithms are available for the important special case of three dimensions, where time in fact suffices. For three or higher dimensions, I recommend that you use one of the codes described below rather than roll your own.

• Is your data given as vertices or half-spaces? - The problem of finding the intersection of a set of n half-spaces in d dimensions is dual to that of computing convex hulls of n points in d dimensions. Thus the same basic algorithm suffices for both problems. The necessary duality transformation is discussed in Section .   
• How many points are likely to be on the hull? - If your points are selected ``randomly'', it is likely that most of them lie within the interior of the hull. Planar convex hull programs can be made more efficient in practice using the observation than the leftmost, rightmost, topmost, and bottommost points must all be on the convex hull. Unless the topmost is leftmost and bottommost is rightmost, this gives a set of either three or four distinct points, defining a triangle or quadrilateral. Any point inside this region cannot be on the convex hull and can be discarded in a linear sweep through the points. Ideally, only a few points will then remain to run through the full convex hull algorithm.

  This trick can also be applied beyond two dimensions, although it loses effectiveness as the dimension increases.

• How do I find the shape of my point set? - Although convex hulls provide a gross measure of shape, any details associated with concavities are lost. For example, the shape of the `G' would be indistinguishable from the shape of the `O'. A more general structure, called alpha-shapes, can be parameterized so as to retain arbitrarily large concavities. Implementations and references on alpha-shapes are included below.   

The primary convex hull algorithm in the plane is the Graham scan. Graham scan starts with one point p known to be on the convex hull (say the point with lowest x-coordinate) and sorts the rest of the points in angular order around p. Starting with a hull consisting of p and the point with the smallest angle, we proceed counterclockwise around v adding points. If the angle formed by the new point and the last hull edge is less than 180 degrees, we add this new point to the hull. If the angle formed by the new point and the last ``hull'' edge is greater than 180 degrees, then a chain of vertices starting from the last hull edge must be deleted to maintain convexity. The total time is , since the bottleneck is sorting the points around v.  

The basic Graham scan procedure can also be used to construct a nonself-intersecting (or simple) polygon passing through all the points. Sort the points around v, but instead of testing angles simply connect the points in angular order. Connecting this to v gives a polygon without self-intersection, although it typically has many skinny protrusions.   

The gift-wrapping algorithm becomes especially simple in two dimensions, since each ``facet'' becomes an edge, each ``edge'' becomes a vertex of the polygon, and the ``breadth-first search'' simply walks around the hull in a clockwise or counterclockwise order. The 2D gift-wrapping, or Jarvis march, algorithm runs in O(n h) time, where h is the number of vertices on the convex hull. I would recommend sticking with Graham scan unless you really know in advance that there cannot be too many vertices on the hull.

Implementations: O'Rourke [O'R94] provides a robust implementation of the Graham scan in two dimensions and an implementation of an incremental algorithm for convex hulls in three dimensions. Both are written in C. The latter has been proven capable of solving 10,000-point problems in a few minutes on a modern workstation. See Section .

Qhull [BDH97] appears to be the convex hull code of choice for general dimensions (in particular from 2 to about 8 dimensions). It is written in C and can also construct Delaunay triangulations, Voronoi vertices, furthest-site Voronoi vertices, and half-space intersections. Qhull has been widely used in scientific applications and has a well-maintained home page at http://www.geom.umn.edu/software/qhull/.    

An alternative higher-dimensional convex hull code in ANSI C is Ken Clarkson's Hull, available at http://www.cs.att.com/netlib/voronoi/hull.html. It does not appear to be as widely used or actively maintained as Qhull, but it also does alpha-shapes.   For an excellent alpha-shapes code, originating from the work of Edelsbrunner and Mucke [EM94], check out http://fiaker.ncsa.uiuc.edu/alpha/.

Fukuda's cdd program is the best choice for nonsimplicial polytopes in about 6D and higher. See ftp://ifor13.ethz.ch/pub/fukuda/cdd/. It may be used for computing convex hulls and half-space intersection.  

XTango (see Section ) provides animations of the Graham scan and Jarvis march algorithms in the plane.  

A Pascal implementation of Graham scan appears in [MS91]. See Section . C++ implementations of planar convex hulls includes LEDA (see Section ).    Algorithm 523 [Edd77] of the Collected Algorithms of the ACM is a Fortran code for planar convex hulls. It is available from Netlib (see Section ).   

Notes: Constructing planar convex hulls plays a similar role in computational geometry as sorting does in algorithm theory. Like sorting, convex hull is a fundamental problem for which a wide variety of different algorithmic approaches lead to interesting or optimal algorithms. Preparata and Shamos [PS85] give a good exposition of several such algorithms, including quickhull and mergehull, both inspired by the sorting algorithms. In fact, a simple construction involving points on a parabola reduces sorting to convex hull, so the information-theoretic lower bound for sorting implies that planar convex hull requires time to compute. A stronger lower bound is established in [Yao81].  

Good expositions of the Graham scan algorithm [Gra72] and the Jarvis march [Jar73] include [CLR90, PS85]. The gift wrapping algorithm was introduced by Chand and Kapur [CK70]. Noteworthy among planar convex hull algorithms is Seidel and Kirkpatrick [KS86], which takes time, where h is the number of hull vertices, which captures the best performance of both Graham scan and gift wrapping and is (theoretically) better in between.

Alpha-hulls, introduced in [EKS83], provide a useful notion of the shape of a point set. A generalization to three dimensions, with an implementation, is presented in [EM94].

Reverse-search algorithms for constructing convex hulls are effective in higher dimensions [AF92], although constructions demonstrating the poor performance of convex hull algorithms for nonsimplicial polytopes are presented in [AB95]. Through a clever lifting-map construction [ES86], the problem of building Voronoi diagrams in d-dimensions can be reduced to constructing convex hulls in (d+1)-dimensions. See Section for more details.    

Dynamic algorithms for convex-hull maintenance are data structures that permit inserting and deleting arbitrary points while always representing the current convex hull. The first such dynamic data structure [OvL81] supported insertions and deletions in time. Expositions of this result include [PS85].  

Related Problems: Sorting (see page ), Voronoi diagrams (see page ).