Convex hull: elastic band analogy 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. The elastic band contracts to form the hull of the convex. ...
The elastic band contracts to form the hull of the convex. ...
Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ...
Look up real in Wiktionary, the free dictionary. ...
In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ...
Look up Convex set in Wiktionary, the free dictionary. ...
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 (minimumenergy) 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 3dimensional 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. In mathematics, curvature refers to a number of loosely related concepts in different areas of geometry. ...
Hyperbolic parabloid A model of an ellyptic hyperboloid of one sheet A saddle surface is a smooth surface all points of which are saddle 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 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 , where n is an arbitrary natural number, the numbers t_{j} are nonnegative and sum to 1, and the points x_{j} are in X. It is simple to check that this set satisfies either of the two definitions above. So the convex hull H_{convex}(X) of set X is: A convex combination is a linear combination of data points (which can be vectors or scalars) where all coefficients are positive and sum up to 1. ...
In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ...
In fact, if X is a subset of an Ndimensional 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. In geometry, a simplex (plural: simplices) or nsimplex is an ndimensional analogue of a triangle. ...
An illustration of CarathÃ©odorys theorem for a square in R2 See also CarathÃ©odorys theorem for other meanings In mathematics CarathÃ©odorys theorem on convex sets states that if a point x of Rd lies in the convex hull of a set P, there is a...
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 twodimensional plane or threedimensional 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. 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. ...
In computer science, computational geometry is the study of algorithms to solve problems stated in terms of geometry. ...
Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ...
Computing the convex hull means that a nonambiguous 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. A binary tree, a simple type of branching linked data structure. ...
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). In mathematics, and computational geometry, a Delaunay triangulation or Delone triangularization for a set P of points in the plane is a triangulation DT(P) such that no point in P is inside the circumcircle of any triangle in DT(P). ...
In mathematics, duality has numerous meanings. ...
This is the Voronoi diagram of a random set of points in the plane (all points lie within the image). ...
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 axisparallel 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. The orthogonal convex hull of a point set In Euclidean geometry, a set is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single...
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 computationalgeometric 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 socalled "rotatingcalipers" method can be used to move efficiently from one hull vertex to another. Pattern recognition is a field within the area of machine learning. ...
UPIICSA IPN  Binary image Image processing is any form of information processing for which the input is an image, such as photographs or frames of video; the output is not necessarily an image, but can be for instance a set of features of the image. ...
A graph of a Normal bell curve showing statistics used in educational assessment and comparing various grading methods. ...
A geographic information system (GIS) is a system for managing data that has a spatial specialized form of an information system. ...
See also In mathematics, more precisely in complex analysis, the holomorphically convex hull of a given compact set in the ndimensional complex space Cn is defined as follows. ...
In mathematics, the affine hull of a set S in Euclidean space Rn is the smallest affine set containing S, or equivalently, the intersection of all affine sets containing S. Here, an affine set may be defined as the translation of a vector subspace. ...
In the mathematical subfield of linear algebra, the linear span, also called the linear hull, of a set of vectors in a vector space is the intersection of all subspaces containing that set. ...
The orthogonal convex hull of a point set In Euclidean geometry, a set is defined to be orthogonally convex if, for every line L that is parallel to one of the axes of the Cartesian coordinate system, the intersection of K with L is empty, a point, or a single...
References  Brown, K. Q. (1979). "Voronoi diagrams from convex hulls". Information Processing Letters 9 (5): 223–228.
 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.
Thomas H. Cormen is the coauthor of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ...
Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ...
Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ...
Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ...
Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ...
Franco P. Preparata (born December 1935) is a computer scientist, the An Wang Professor of Computer Science at Brown University. ...
Prof Dr. Mark H. Overmars (born 29 September 1958) is a Dutch programmer and teacher of programming (particularly of games). ...
External links  Applet for calculation and visualization of convex hull, Delaunay triangulations and Voronoi diagrams in space
 Mathworld on convex hull
 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
