Convex Hull, Convex Hull

Unless the points are collinear, the convex hull in this sense is a simple closed polygonal chain.

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.

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.

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 Carathodory's theorem.

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.

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.

Source: Wikipedia > Convex Hull