Convex hull
From Wikipedia, the free encyclopedia
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X. (Note that X may be the union of any set of objects made of points).
To show this exists, it is necessary to see that every X is contained in at least one convex set (the whole space V, for example), and any intersection of convex sets containing X is also a convex set containing X. It is then clear that the convex hull is the intersection of all convex sets containing X, which is an alternative definition.
More directly, the convex hull of X can be described constructively as the set of convex combinations of points from X: that is, the set of points of the form 
, where n is an arbitrary natural number, the numbers tj are non-negative and sum to 1, and the points xj are in X. It is simple to check that this set satisfies either of the two definitions above.
In fact, if X is a subset of an N-dimensional vector space, sums of up to N+1 points are sufficient in the definition above. This is equivalent to saying that the convex hull of X is the union of all simplexes with at most N+1 vertices from X. This is known as Carathéodory's theorem.
The convex hull is defined for any kind of objects made up of points in a vector space, which may have any number of dimensions. The convex hull of finite sets of points and other geometrical objects in a two-dimensional plane or three-dimensional space are special cases of practical importance.
Contents |
[edit] Intuitive picture
For planar objects, i.e., lying in the plane, the convex hull may be easily visualized by imagining an elastic band stretched open to encompass the given objects; when released, it will assume the shape of the required convex hull.
It may seem natural to generalise this picture to higher dimensions by imagining the objects enveloped in a sort of idealised unpressurised elastic membrane or balloon under tension. However, the equilibrium (minimum-energy) surface in this case may not be the convex hull — parts of the resulting surface may have negative curvature, like a saddle surface. For the case of points in 3-dimensional space, if a rigid wire is first placed between each pair of points, then the balloon will spring back under tension to take the form of the convex hull of the points.
[edit] Computation of convex hulls
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.
[edit] Planar case
[edit] Finite set of points
If not all points are on the same line, then their convex hull is a convex polygon. 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.
[edit] 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)
[edit] 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.
[edit] 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.
[edit] 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 is called the ultimate convex hull algorithm and was introduced by Kirkpatrick and Seidel in 1986, and uses the principle of marriage-before-conquest. A much simpler algorithm was developed by Chan in 1996, and is called Chan's algorithm.
[edit] 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.
[edit] 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 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.
[edit] 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. 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.
[edit] Relations to other geometric structures
The Delaunay triangulation of a point set and its dual, the Voronoi Diagram, are mathematically related to convex hulls: the Delaunay triangulation of a point set in Rn can be viewed as the projection of a convex hull in Rn+1 (Brown 1979).
The orthogonal convex hull of a point set is the intersection of all orthogonally convex supersets of the point set, where an orthogonally convex set is defined to intersect each axis-parallel line in a connected subset. Orthogonal convex hulls have properties similar to those of convex hulls, and can be constructed by algorithms with similar time bounds as those for convex hulls.
[edit] Applications
The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics and GIS. It also serves as a tool, a building block for a number of other computational-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 O(n log n). 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.
[edit] See also
[edit] References
- Brown, K. Q. (1979). "Voronoi diagrams from convex hulls". Information Processing Letters 9 (5): 223–228.
- 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.
- M. de Berg; M. van Kreveld; Mark Overmars; O. Schwarzkopf. (2000). Computational Geometry, Algorithms and Applications. Springer.
