Convex Hull

In mathematics, the convex hull or convex envelope of a set X of points in the Euclidean plane or Euclidean space is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape formed by a rubber band stretched around X.

Formally, the convex hull may be defined as the intersection of all convex sets containing X or as the set of all convex combinations of points in X. With the latter definition, convex hulls may be extended from Euclidean spaces to arbitrary real vector spaces; they may also be generalized further, to oriented matroids.

The algorithmic problem of finding the convex hull of a finite set of points in the plane or in low-dimensional Euclidean spaces is one of the fundamental problems of computational geometry.

Read more about Convex HullDefinitions, Convex Hull of A Finite Point Set, Computation of Convex Hulls, Minkowski Addition and Convex Hulls, Relations To Other Structures, Applications

Other articles related to "convex hull, convex hulls, convex":

Convex Hull Algorithms - Planar Case - Simple Polygon
... were first to provide a correct algorithm to construct the convex hull of a simple polygon in O(n) time ... The leftmost vertex is on the convex hull and we denote it ... The second point is assumed to be a candidate convex hull vertex as well ...
Convex Hull Algorithms
... Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science, see "Convex hull applications" ... 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 ...
Local Convex Hull
... Local convex hull (LoCoH) is a method for estimating the size the home range of an animal or a group of animals (e.g ... On the other hand, if the local kernel element associated with each point is a local convex polygon constructed from the point and its k-1 nearest neighbors, then ... Construct a convex hull for each set of nearest neighbors and the original data point ...
Schönhardt Polyhedron - Construction
... The convex hull of these two triangles forms a convex polyhedron that is combinatorially equivalent to a regular octahedron along with the triangle edges, it has six edges ... the three connecting edges, and replacing them by the three diagonals of the convex hull ... can be formed by removing three disjoint tetrahedra from this convex hull each of the removed tetrahedra is the convex hull of four vertices from the two triangles, two from each triangle ...
Convex Hull - 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 ...