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.
Contents |
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 object; 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.
Existence of the convex hull
To show that the convex hull of a set X in a real vector space V exists, notice that 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. This can be used as an alternative definition of the convex hull. 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 <math>\sum_{j=1}^n t_jx_j</math>, where n is an arbitrary natural number, the numbers <math>t_j</math> are non-negative and sum to 1, and the points <math>x_j</math> are in X. It is simple to check that this set satisfies either of the two definitions above. So the convex hull <math>H_\mathrm{convex}(X)</math> of set X is: <math> H_\mathrm{convex}(X) =\left\{\sum_{i=1}^k \alpha_i x_i \ \Bigg | \ x_i\in X, \, \alpha_i\in \mathbb{R}, \, \alpha_i \geq 0, \, \sum_{i=1}^k \alpha_k=1,\, k=1, 2, \dots\right\}. </math> 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.
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.
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.
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.
See also
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.
External links
- Applet for calculation and visualization of convex hull, Delaunay triangulations and Voronoi diagrams in space
- Mathworld on convex hull
- "Convex Hull" by Eric W. Weisstein, The Wolfram Demonstrations Project, 2007.
- 2D, 3D, and dD Convex Hull in CGAL, the Computational Geometry Algorithms Library
- Qhull code for Convex Hull, Delaunay Triangulation, Voronoi Diagram, and Halfspace Intersection
- C++ Code and Reports for Convex Hull
