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 {konvex} }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}$

Web links

• General information on convex hulls including algorithms for calculation
• Java applet for convex hull
• About the randomized algorithm (PDF, 81 kB)
• Java applet to demonstrate the computation of the convex hull of a given point set with the help of the algorithms "Sweep", "Jarvis March" and "Graham Scan"
• Java applet for the interactive implementation of the "sweep" algorithm

literature

1. ^ Franco P. Preparata and Michael Ian Shamos : Computational Geometry - An Introduction . Springer-Verlag , 1985, 1st edition: ISBN 0-387-96131-3 ; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3 ; Russian translation, 1989: ISBN 5-03-001041-6 .