# Convex hull

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*.

In computational geometry, it is common to use the term "convex hull" for the *boundary* of the minimal convex set containing a given non-empty finite set of points in the plane. Unless the points are collinear, the convex hull in this sense is a simple closed polygonal chain.

## 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 (see article about minimal surfaces for examples). 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 finite subsets of points from *X*: that is, the set of points of the form , where *n* is an arbitrary natural number, the numbers are non-negative and sum to 1, and the points are in *X*. It is simple to check that this set satisfies either of the two definitions above.
So the convex hull of set X is:

In fact, if *X* is a subset of an *N*-dimensional vector space, convex combinations of at most *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, including infinite-dimensional vector spaces. 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, including:

- direct method
- Wrapping (Packaging) method
- Graham's scan method
- Incremental (Sequential addition) method
- Divide and Conquer method
- Quick method (equivalent to Quick Sort)
- Inner point elimination

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

*, the number of points on the convex hull.*

**h**## 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 **R**^{n} can be viewed as the projection of a convex hull in **R**^{n+1} (Brown 1979).

## Applications

The problem of finding convex hulls finds its practical applications in pattern recognition, image processing, statistics, GIS and static code analysis by abstract interpretation. It also serves as a tool, a building block for a number of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.

## See also

- Holomorphically convex hull
- Orthogonal convex hull
- Affine hull
- Linear hull
- Oloid

## References

- Brown, K. Q. (1979). "Voronoi diagrams from convex hulls".
*Information Processing Letters***9**(5): 223–228. doi: .

- 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
- Weisstein, Eric W.
*Convex Hull*. From MathWorld--A Wolfram Web Resource. Accessed 15 June 2010. - "Convex Hull" by Eric W. Weisstein, Wolfram Demonstrations Project, 2007.
- Demo as Java Applet, with source code
- Appropriate problem at SPOJ - check your implementation.