FACTOID # 10: The total number of state executions in 2005 was 60: 19 in Texas and 41 elsewhere. The racial split was 19 Black and 41 White.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Convex hull
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. 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. ...

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. 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 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. 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_{convex}(X) =left{sum_{i=1}^k alpha_i x_i  Bigg |  x_iin X, , alpha_iin mathbb{R}, , alpha_i geq 0 , sum_{i=1}^k alpha_k=1,, k=1, 2, dotsright}. 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 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. In geometry, a simplex (plural: simplices) or n-simplex is an n-dimensional 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 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. 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 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. 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 Rn can be viewed as the projection of a convex hull in Rn+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 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. 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 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. 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 n-dimensional 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 co-author 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

  Results from FactBites:
 
hull - convex hulls, Delaunay triangulations, alpha shapes (878 words)
Hull is an ANSI C program that computes the convex hull of a point set in general (but small!) dimension.
The input is a list of points, and the output is a list of facets of the convex hull of the points, each facet presented as a list of its vertices.
If the convex hull is a single point, the algorithm will fail to report it.
Convex hull - Wikipedia, the free encyclopedia (1212 words)
This is equivalent to saying that the convex hull is the union of all simplexes with vertices in X. This is known as Carathéodory's theorem.
Computing the convex hull means that a non-ambiguous and efficient representation of the required convex shape is constructed.
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.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m