# Convex hull

The blue set is the convex hull of the red set

The convex hull of a subset is the smallest convex set that contains the initial set. This object is viewed in various mathematical disciplines such as convex analysis.

## Definitions

The convex hull of a subset of a real or complex vector space${\ displaystyle X}$ ${\ displaystyle V}$

${\ displaystyle \ operatorname {conv} X: = \ bigcap _ {X \ subseteq K \ subseteq V \ atop K \ \ mathrm {convex}} K}$

is defined as the intersection of all convex supersets of . It is itself convex and thus the smallest convex set that contains. The formation of the convex hull is a hull operator . ${\ displaystyle X}$${\ displaystyle X}$

The convex hull can also be described as the set of all finite convex combinations :

${\ displaystyle \ operatorname {conv} X = \ left \ {\ left. \ sum _ {i = 1} ^ {n} {\ alpha _ {i} \ cdot x_ {i}} \ right | x_ {i} \ in X, n \ in \ mathbb {N}, \ sum _ {i = 1} ^ {n} \ alpha _ {i} = 1, {\ alpha _ {i}} \ geq 0 \ right \}}$

The conclusion of the convex hull is the intersection of all the closed half-spaces that completely contain. The convex hull of two points is their connecting line: ${\ displaystyle X}$${\ displaystyle a, b}$

${\ displaystyle \ operatorname {conv} \ {a, b \} = {\ overline {ab}}: = \ {\ lambda a + (1- \ lambda) b \ mid 0 \ leq \ lambda \ leq 1 \}}$

The convex hull of finitely many points is a convex polytope .

## Examples

Convex hull of the points marked in red in two-dimensional space
• The adjacent picture shows the convex hull of the points (0,0), (0,1), (1,2), (2,2) and (4,0) in the plane. It consists of the area outlined in red (including the border).
• There is a class of curves (including the Bézier curve ), the members of which meet the so-called "Convex Hull Property" (CHP), i.e. H. their image runs entirely within the convex hull of their control points.

## Calculation in the two-dimensional case

The determination of the convex hull of points im has an asymptotic running time of as lower bound ; the proof is done by reducing to sorting numbers. If only the points lie on the edge of the convex hull, the limit is included . ${\ displaystyle n}$${\ displaystyle \ mathbb {R} ^ {2}}$${\ displaystyle \ Omega (n \ log n)}$${\ displaystyle n}$${\ displaystyle k}$${\ displaystyle n}$${\ displaystyle \ Omega (n \ log k)}$

There are several algorithms for the calculation:

• Graham scan algorithm with runtime${\ displaystyle {\ mathcal {O}} (n \ log n)}$
• Jarvis-March (2d gift wrapping algorithm ) with runtime , where the number of points is on the edge of the envelope${\ displaystyle {\ mathcal {O}} (nk)}$${\ displaystyle k}$
• QuickHull based on Quicksort with expected runtime ; Worst case${\ displaystyle {\ mathcal {O}} (n \ log n)}$ ${\ displaystyle {\ mathcal {O}} (n ^ {2})}$
• Incremental algorithm with runtime ${\ displaystyle {\ mathcal {O}} (n \ log n)}$
• Chan's algorithm with running time , where the number of points is on the edge of the envelope.${\ displaystyle {\ mathcal {O}} (n \ log k)}$${\ displaystyle k}$