Convex hull algorithms
Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science, see "Convex hull applications".
In computational geometry, numerous algorithms are proposed for computing the convex hull of a finite set of points, with various computational complexities.
Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. The complexity of the corresponding algorithms is usually estimated in terms of n, the number of input points, and h, the number of points on the convex hull.
Planar case
Finite set of points
If not all points are on the same line, then their convex hull is a convex polygon whose vertices are some of the points in the input set. Its most common representation is the list of its vertices ordered along its boundary clockwise or counterclockwise. In some applications it is convenient to represent a convex polygon as an intersection of a set of half-planes.
Jarvis march
The simplest (although not the most time-efficient in the worst case) algorithm in the plane was proposed by R.A. Jarvis in 1973. It is also called gift wrapping algorithm. It has O(nh) time complexity, where n is the number of points in the set, and h is the number of points in the hull. In the worst cases the complexity is O(n2)
Graham scan
A slightly more sophisticated, but much more efficient algorithm is the Graham scan, published in 1972 (O(n log n) time complexity). If the points are already sorted by one of the coordinates or by the angle to a fixed vector, then the algorithm takes O(n) time.
Pseudocode example
GrahamScan(list R) {
int element = 2; // We start from the third coordinate in the list
do {
if ( last three point make a left turn )
element++
else
delete R[element]
}
while (element is not at the end of the list)
return R;
}
Divide and conquer
Another O(n log n) solution is the divide and conquer algorithm for the convex hull, published in 1977 by Preparata and Hong. This algorithm is also applicable to the three dimensional case.
Pseudocode example
dcHull (list P) {
coordinateList O, listOne, listTwo;
if (P.size() <= 5)
return doGrahamHull(P);
else
{
split(P,listOne,listTwo); // divide the list into two lists - Divide
return merge(dcHull(listOne),dcHull(listTwo)); // Now recursively call the split strings - Conquer
}
}
Optimal output-sensitive algorithms
While it is not possible to do better than O(n log n) if we write the complexity only as a function of the input size n, we can obtain more efficient solutions by using an output-sensitive algorithm. There are two famous optimal output-sensitive algorithms for the planar case with O(n log h) time complexity, where h is the number of points in the hull. The earliest one was introduced by Kirkpatrick and Seidel in 1986 (who called it "the ultimate convex hull algorithm"). A much simpler algorithm was developed by Chan in 1996, and is called Chan's algorithm.
Akl-Toussaint heuristics
The following simple heuristic is often used as the first step in implementations of convex hull algorithms to improve their performance. It is based on the efficient convex hull algorithm by S. Akl and G. T. Toussaint, 1978. The idea is to quickly exclude many points that would not be part of the convex hull anyway. This method is based on the following idea. Find the two points with the lowest and highest x-coordinates, and the two points with the lowest and highest y-coordinates. (Each of these operations takes O(n).) These four points form a convex quadrilateral, and all points that lie in this quadrilateral (except for the four initially chosen vertices) are not part of the convex hull. Finding all of these points that lie in this quadrilateral is also O(n), and thus, the entire operation is O(n). Optionally, the points with smallest and largest sums of x- and y-coordinates as well as those with smallest and largest differences of x- and y-coordinates can also be added to the quadrilateral, thus forming an irregular convex octagon, whose insides can be safely discarded.
Simple polygon
The convex hull of a simple polygon can be constructed in O(n) time. The basic idea is very simple. Starting from the leftmost vertex, at each step one looks at three consecutive vertices of the polygon. If the resulting angle is concave, then the middle point is discarded and the next (along the polygon) vertex is added to the triple to be tested. If the angle is convex, then the whole triple is shifted by one vertex along the polygon. However quite a few published articles overlooked a possibility that deletion of a vertex from a polygon may result in a self-intersecting polygon, rendering further flow of the algorithm invalid. Fortunately, this case may also be handled efficiently.
Higher dimensions
For a finite set of points, the convex hull is a convex polyhedron in three dimensions, or in general a convex polytope for any number of dimensions whose vertices are some of the points in the input set.. Its representation is not so simple as in the planar case, however. In higher dimensions, even if the vertices of a convex polytope are known, construction of its faces is a non-trivial task.
A number of algorithms are known for the three-dimensional case, as well as for arbitrary dimensions. See http://www.cse.unsw.edu.au/~lambert/java/3d/hull.html. See also David Mount's Lecture Notes for comparison. Refer to Lecture 4 for the latest developments, including Chan's algorithm.
See also
References
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 33.3: Finding the convex hull, pp.947–957.
- Franco P. Preparata, S.J. Hong. Convex Hulls of Finite Sets of Points in Two and Three Dimensions, Commun. ACM, vol. 20, no. 2, pp. 87–93, 1977.
- Mark de Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf (2000). Computational Geometry (2nd revised edition ed.). Springer-Verlag. ISBN 3-540-65620-0.
{{cite book}}:|edition=has extra text (help)CS1 maint: multiple names: authors list (link) Section 1.1: An Example: Convex Hulls (describes classical algorithms for 2-dimensional convex hulls). Chapter 11: Convex Hulls: pp.235–250 (describes a randomized algorithm for 3-dimensional convex hulls due to Clarkson and Shor).