Convex hull

from Wikipedia, the free encyclopedia
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.


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 .


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 .

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


  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 .