next up previous contents index CD CD Algorithms
Next: Triangulation Up: Computational Geometry Previous: Robust Geometric Primitives

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 tex2html_wrap_inline29867 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:

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 tex2html_wrap_inline29879 , 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 tex2html_wrap_inline29883 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 gif.

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    

An alternative higher-dimensional convex hull code in ANSI C is Ken Clarkson's Hull, available at 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

Fukuda's cdd program is the best choice for nonsimplicial polytopes in about 6D and higher. See It may be used for computing convex hulls and half-space intersection.  

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

A Pascal implementation of Graham scan appears in [MS91]. See Section gif. C++ implementations of planar convex hulls includes LEDA (see Section gif).    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 gif).   

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 tex2html_wrap_inline29885 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 tex2html_wrap_inline29887 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 gif 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 tex2html_wrap_inline29891 time. Expositions of this result include [PS85].  

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

next up previous contents index CD CD Algorithms
Next: Triangulation Up: Computational Geometry Previous: Robust Geometric Primitives

Mon Jun 2 23:33:50 EDT 1997