convex hull

English

The convex hull of a random set of points, plotted in 3D

Noun

convex hull (plural convex hulls)

1. (mathematics) The smallest convex set of points in which a given set of points is contained.
   • 1994, David Eppstein, Chapter 10: Average Case Analysis of Dynamic Geometric Optimization, Association of Computing Machinery, Society for Industrial and Applied Mathematics, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, page 83,

     This problem can be solved in time O(n^c) by combining a weight-balanced tree of the convex hull vertices with a farthest neighbor data structure of Agarwal and Matoušek [2].

   • 2005, A.D. Alexandrov, Convex Polyhedra‎^[1], page 23:

     Thus, the polyhedron and the convex hull of the set of its vertices coincide, which was to be proved.
     Since the convex hull of a set M is determined uniquely from M, Theorem 1 implies that a bounded solid polyhedron and its surface, i.e., a closed convex polyhedron, are determined uniquely from its vertices.

   • 2007, Charalambos D. Aliprantis, Kim C. Border, Infinite Dimensional Analysis: A Hitchhiker's Guide, page 185:

     The convex hull of a compact subset of an infinite dimensional topological vector space need not be a compact set.

Synonyms

• (smallest convex set of points containing a given set): convex envelope, linear span, span

Translations

convex set of points

• Finnish: konveksi verho
• French: enveloppe convexe (fr)
• Italian: inviluppo convesso m, involucro convesso m

Further reading

• Convex geometry on Wikipedia.Wikipedia
• Convex set on Wikipedia.Wikipedia