Citizendia
Your Ad Here

Convex hull: elastic band analogy
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. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and In Mathematics, a vector space (or linear space) is a collection of objects (called vectors) that informally speaking may be scaled and added In Euclidean space, an object is convex if for every pair of points within the object every point on the Straight line segment that joins them is also within the

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. Computational geometry is a branch of Computer science devoted to the study of algorithms which can be stated in terms of Geometry. For a different notion of boundary related to Manifolds see that article Unless the points are collinear, the convex hull in this sense is a simple closed polygonal chain. A polygonal chain, polygonal curve, polygonal path, or piecewise linear curve, is a connected series of Line segments More formally a polygonal

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. In Mathematics, curvature refers to any of a number of loosely related concepts in different areas of geometry A saddle surface is a Smooth surface containing one or more Saddle points The term derives of the peculiar shape of historical Saddles evolved 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 \sum_{j=1}^n t_jx_j, where n is an arbitrary natural number, the numbers tj are non-negative and sum to 1, and the points xj are in X. A convex combination is a Linear combination of points (which can be vectors scalars, or more generally points in an Affine space) In Mathematics, a natural number (also called counting number) can mean either an element of the set (the positive Integers or an It is simple to check that this set satisfies either of the two definitions above. So the convex hull Hconvex(X) of set X is:

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_i=1,\, k=1, 2, \dots\right\}.

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. In Geometry, a simplex (plural simplexes or simplices) or n -simplex is an n -dimensional analogue of a triangle This is known as Carathéodory's theorem. See also Carathéodory's theorem for other meanings In Convex geometry Carathéodory's theorem states that if a point x of

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

Main article: Convex hull algorithms

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 Computational geometry is a branch of Computer science devoted to the study of algorithms which can be stated in terms of Geometry. Computational complexity theory, as a branch of the Theory of computation in Computer science, investigates the problems related to the amounts of resources

Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed. A data structure in Computer science is a way of storing Data in a computer so that it can be used efficiently 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). In Mathematics, and Computational geometry, a Delaunay triangulation for a set P of points in the plane is a triangulation DT( P) In Mathematics, duality has numerous meanings Generally speaking duality is a metamathematical involution. In Mathematics, a Voronoi diagram, named after Georgy Voronoi, also called a Voronoi Tessellation, a Voronoi decomposition, or

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. In Euclidean geometry, a set K\subset\R^n is defined to be Orthogonally convex if for every line L that is parallel to one of the axes of the Cartesian 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. Pattern recognition is a sub-topic of Machine learning. It is "the act of taking in raw data and taking an action based on the category of the data" Image processing is any form of Signal processing for which the input is an image such as photographs or frames of video the output of image processing can be either an image Statistics is a mathematical science pertaining to the collection analysis interpretation or explanation and presentation of Data. 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. Rotating calipers is a computational Algorithm developed by Michael Shamos in 1978 for determining all antipodal pairs of points and vertices on a

It is possible to ascertain whether a given point falls within the convex hull of a set of points, in any number of dimensions, without forming and characterizing the convex hull (King and Zeng, 2006).

See also

References

External links

Dictionary

convex hull

-noun

  1. (mathematics) The smallest convex set of points in which a given set of points is contained.
© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
 Dapyx Software network: MP3 Explorer | Ebook Manager | Zenithic