# Convex hull

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

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 .

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

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:

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

## Examples

- 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 .

There are several algorithms for the calculation:

- Graham scan algorithm with runtime
- Jarvis-March (2d gift wrapping algorithm ) with runtime , where the number of points is on the edge of the envelope
- QuickHull based on Quicksort with expected runtime ; Worst case
- Incremental algorithm with runtime
- Chan's algorithm with running time , where the number of points is on the edge of the envelope.

## 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

- ^ 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 .