Convex hull

for two or three dimensional point sets, and in time matching the worst-case output complexity given by the upper bound theorem in higher dimensions.

As well as for finite point sets, convex hulls have also been studied for simple polygons, Brownian motion, space curves, and epigraphs of functions.

Convex hulls have wide applications in mathematics, statistics, combinatorial optimization, economics, geometric modeling, and ethology.

may be defined as[2] For bounded sets in the Euclidean plane, not all on one line, the boundary of the convex hull is the simple closed curve with minimum perimeter containing

[3] This formulation does not immediately generalize to higher dimensions: for a finite set of points in three-dimensional space, a neighborhood of a spanning tree of the points encloses them with arbitrarily small surface area, smaller than the surface area of the convex hull.

[4] However, in higher dimensions, variants of the obstacle problem of finding a minimum-energy surface above a given shape can have the convex hull as their solution.

[6] It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing

For three-dimensional hulls, the upward-facing and downward-facing parts of the boundary form topological disks.

The sets of vertices of a square, regular octahedron, or higher-dimensional cross-polytope provide examples where exactly

Every antimatroid can be represented in this way by convex hulls of points in a Euclidean space of high-enough dimension.

This provides a step towards the Shapley–Folkman theorem bounding the distance of a Minkowski sum from its convex hull.

[3] For sets of points in general position, the convex hull is a simplicial polytope.

Computing the same decomposition recursively for each pocket forms a hierarchical description of a given polygon called its convex differences tree.

[24] Reflecting a pocket across its convex hull edge expands the given simple polygon into a polygon with the same perimeter and larger area, and the Erdős–Nagy theorem states that this expansion process eventually terminates.

, there will be times during the Brownian motion where the moving particle touches the boundary of the convex hull at a point of angle

[32] In two dimensions, it may suffice more simply to list the points that are vertices, in their cyclic order around the hull.

For points in two and three dimensions, more complicated output-sensitive algorithms are known that compute the convex hull in time

[34] The convex hull of a simple polygon in the plane can be constructed in linear time.

[37] The construction of convex hulls also serves as a tool, a building block for a number of other computational-geometric algorithms such as the rotating calipers method for computing the width and diameter of a point set.

[46] The alpha shapes of a finite point set give a nested family of (non-convex) geometric objects describing the shape of a point set at different levels of detail.

They are used in robust statistics as the outermost contour of Tukey depth, are part of the bagplot visualization of two-dimensional data, and define risk sets of randomized decision rules.

And in the study of animal behavior, convex hulls are used in a standard definition of the home range.

[50] In spectral analysis, the numerical range of a normal matrix is the convex hull of its eigenvalues.

The boundaries of convex hulls of ideal points of three-dimensional hyperbolic space are analogous to ruled surfaces in Euclidean space, and their metric properties play an important role in the geometrization conjecture in low-dimensional topology.

In robust statistics, the convex hull provides one of the key components of a bagplot, a method for visualizing the spread of two-dimensional sample points.

The contours of Tukey depth form a nested family of convex sets, with the convex hull outermost, and the bagplot also displays another polygon from this nested family, the contour of 50% depth.

[60] In geometric modeling, one of the key properties of a Bézier curve is that it lies within the convex hull of its control points.

This so-called "convex hull property" can be used, for instance, in quickly detecting intersections of these curves.

It differs from the skin girth, the perimeter of the cross-section itself, except for boats and ships that have a convex hull.

In a set of energies of several stoichiometries of a material, only those measurements on the lower convex hull will be stable.

The convex hull of the red set is the blue and red convex set .
Convex hull of a bounded planar set: rubber band analogy
3D convex hull of 120 point cloud
The witch of Agnesi . The points on or above the red curve provide an example of a closed set whose convex hull is open (the open upper half-plane ).
Convex hull of points in the plane
Convex hull ( in blue and yellow) of a simple polygon (in blue)
An oloid , the convex hull of two circles in 3d space
Partition of seven points into three subsets with intersecting convex hulls, guaranteed to exist for any seven points in the plane by Tverberg's theorem
A bagplot . The outer shaded region is the convex hull, and the inner shaded region is the 50% Tukey depth contour.
Convex hull of magnesium – carbon compounds. [ 68 ] Mg 2 C 3 is expected to be unstable as it lies above the lower hull.