Convex Hull

A Convex Hull is a convex set that contains a point set.

• AKA: Convex Envelope, Convex Closure.
• Context:
  • It can range from being a Closed Convex Hull to being an Open Convex Hull.
  • It can range from being an Orthogonal Convex Hull to being a Relative Convex Hull.
  • It can be generated by a Convex Hull Algorithm.
  • …
• Example(s):
  • a Bagplot,
  • a 2D Convex Hull,
  • a 3D Convex Hull,
  • a Convex Skull,
  • a Holomorphically Convex Hull
  • an Oloid.
  • a ROC Convex Hull,
  • a Simple Polygon Convex Hull.
  • …
• Counter-Example(s):
  • an Affine Hull,
  • a Conical Hull.
  • a Linear Hull,
  • Delaunay Triangulation,
  • Voronoi Diagram.
• See: Lower Convex Envelope Function, Convex Function, Convex Layer, Computational Geometry, Combinatorial Optimization, Euclidean Plane, Euclidean Space, Bounded_Set, Convex Combination, Real Vector Space, Oriented Matroid, Closure Operator, Minkowski Sum, Projective Duality, Finite Point Set, Polygon, Brownian Motion, Space Curve, Tverberg's Theorem.

---

---

References

2020

• (Wikipedia, 2020) ⇒ https://en.wikipedia.org/wiki/Convex_hull Retrieved:2020-3-29.
  • In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. For a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around the subset.

    Formally, the convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space, or equivalently as the set of all convex combinations of points in the subset. Convex hulls of open sets are open, and convex hulls of compact sets are compact. Every convex set is the convex hull of its extreme points. The convex hull operator is an example of a closure operator, and every antimatroid can be represented by applying this closure operator to finite sets of points.

    The algorithmic problems of finding the convex hull of a finite set of points in the plane or other low-dimensional Euclidean spaces, and its dual problem of intersecting half-spaces, are fundamental problems of computational geometry. They can be solved in time [math]\displaystyle{ O(n\log n) }[/math] for two or three dimensional point sets, and in time matching the worst-case output complexity given by the upper bound theorem in higher dimensions. Convex hulls have also been studied for simple polygons, Brownian motion, space curves, and epigraphs of functions.

    Convex hulls have wide applications in mathematics, statistics, combinatorial optimization, economics, geometric modeling, and ethology. Related structures include the orthogonal convex hull, convex layers, Delaunay triangulation and Voronoi diagram, and convex skull.

---