Convex Hull: Exploring Convex Hull in Computer Vision

By Fouad Sabry

What is Convex Hull

The convex hull, convex envelope, or convex closure of a shape is the smallest convex set that contains the shape. This concept is used in the field of geometry. It is possible to define the convex hull in two different ways: either as the intersection of all convex sets that contain a particular subset of a Euclidean space, or, more precisely, as the set of all convex combinations of points that are contained within the subset. The convex hull of a bounded subset of the plane can be seen as the form that is encompassed by a rubber band that is stretched around the subset.

How you will benefit

(I) Insights, and validations about the following topics:

Chapter 1: Convex hull

Chapter 2: Convex set

Chapter 3: Polyhedron

Chapter 4: Polytope

Chapter 5: Minkowski addition

Chapter 6: Duality (mathematics)

Chapter 7: Carathéodory's theorem (convex hull)

Chapter 8: Curvilinear perspective

Chapter 9: Radon's theorem

Chapter 10: Convex polytope

(II) Answering the public top questions about convex hull.

(III) Real world examples for the usage of convex hull in many fields.

Who this book is for

Professionals, undergraduate and graduate students, enthusiasts, hobbyists, and those who want to go beyond basic knowledge or information for any kind of Convex Hull.

• Language: English
• Publisher: One Billion Knowledgeable
• Release date: May 5, 2024

Book preview

Chapter 1: Convex hull

The convex hull, convex envelope, or convex closure of a shape in geometry is the smallest convex set that contains the shape. The convex hull may be defined as the intersection of all convex sets containing a particular subset of a Euclidean space, or as the set of all convex combinations of points in the subset. For a bounded subset of the plane, the convex hull can be seen as the form contained by an extended rubber band.

Open are the convex hulls of open sets, and compact sets have convex hulls that are compact.

Each convex compact set is the convex hull of its extremities.

The convex hull operator is a closure operator example, Every antimatroid can be represented by applying this closure operator to finite point sets.

Finding the convex hull of a finite number of points in the plane or other low-dimensional Euclidean spaces presents algorithmic challenges, and the twofold issue of overlapping half-spaces, are essential computational geometry problems.

They can be solved in time O(n\log n) 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 explored for simple polygons, Brownian motion, space curves, and the epigraphs of functions, in addition to finite point sets. In mathematics, statistics, combinatorial optimization, economics, geometric modeling, and ethology, convex hulls have numerous uses. Convex skull, orthogonal convex hull, convex layers, Delaunay triangulation, and Voronoi diagram are related structures.

A collection of points in a Euclidean space is convex if it contains the line segments connecting each pair of its points.

The convex hull of a given set X may be defined as

The (unique) minimal convex set containing X

The intersection of all convex sets containing X

The set of all convex combinations of points in X

The union of all simplices with vertices in X

For sets that are limited in the Euclidean plane, not in a single line, the boundary of the convex hull is the simple closed curve with minimum perimeter containing X .

One may imagine stretching a rubber band so that it surrounds the entire set S and then releasing it, allowing it to shrink; when it tightens up, it encloses the convex hull of S .

For three-dimensional objects, the initial definition of the convex hull specifies that it is the smallest possible convex bounding volume. The definition using intersections of convex sets can be extended to non-Euclidean geometry, and the definition using convex combinations can be extended from Euclidean spaces to arbitrary real vector spaces or affine spaces; convex hulls can also be abstractly generalized to oriented matroids.

It is not obvious that the first definition makes sense: why should there exist a unique minimal convex set containing X , for every X ? However, the second meaning, the intersection of all convex sets containing X , is clearly defined.

It is a subset of every other convex set Y that contains X , because Y is included among the sets being intersected.

Thus, it is exactly the unique minimal convex set containing X .

Therefore, The initial two definitions are identical.

Each convex set containing X must (by the assumption that it is convex) contain all convex combinations of points in X , so the set of all convex combinations is contained in the intersection of all convex sets containing X .

Conversely, the set of all convex combinations is itself a convex set containing X , so it also contains the intersection of all convex sets containing X , so the second and third definitions have the same meaning.

In fact, according to Carathéodory's theorem, if X is a subset of a d -dimensional Euclidean space, every convex combination of finitely many points from X is also a convex combination of at most d+1 points in X .

The set of convex combinations of a (d+1) -tuple of points is a simplex; In two dimensions, it is a triangle, whereas in three dimensions it is a tetrahedron.

Therefore, every convex combination of points of X belongs to a simplex whose vertices belong to X , equal to the third and fourth definitions.

In two dimensions, the convex hull is sometimes divided into two sections, the upper hull and the lower hull, extending from the hull's leftmost and rightmost points. In general, one can divide the border of convex hulls of any dimension into upward-facing points (points for which an upward ray is discontinuous from the hull), downward-facing points, and extremal points. The upward- and downward-facing portions of the boundary for three-dimensional hulls form topological disks.

The closed convex hull of a set is the convex hull's closure, while the open convex hull is the interior (or in some sources, the relative interior) of the convex hull.

The closed convex hull of X is the intersection of all closed half-spaces containing X .

If the convex hull of X is already a closed set itself (as happens, for instance, if X is a finite set or more generally a compact set), Consequently, it is identical to the closed convex hull.

However, A closed intersection of half-spaces is itself closed, Therefore, a non-closed convex hull cannot be represented in this manner.

If the open convex hull of a set X is d -dimensional, then every point of the hull belongs to an open convex hull of at most 2d points of X .

The sets of a square's vertices, regular octahedron, or higher-dimensional cross-polytope provide examples where exactly 2d points are needed.

The convex hull of an open set is always itself open from a topological standpoint, whereas the convex hull of a compact set is always itself compact. There are, however, closed sets whose convex hull is not closed. Specifically, the closed set

{\displaystyle \left\{(x,y)\mathop {\bigg |} y\geq {\frac {1}{1+x^{2}}}\right\}}

The convex hull of (the collection of points that lie on or above the witch of Agnesi) is the open upper half-plane.

A convex set's extreme point is a point that does not lie on any open line segment between any other two points in the set. Every extreme point of a convex hull must be included in the supplied set; otherwise, it cannot be created as a convex combination of specified points. Every compact convex set in a Euclidean space (or more generally in a locally convex topological vector space) is the convex hull of its extreme points, according to the Krein–Milman theorem.

The convex-hull operator possesses the attributes of a closure operator:

It is considerable, meaning that the convex hull of every set X is a superset of X .

It does not decrease, meaning that, for every two sets X and Y with X\subseteq Y , the convex hull of X is a subset of the convex hull of Y .

It is irreversible, meaning that for every X , the convex hull of the convex hull of X is the same as the convex hull of X .

This is the closure operator of an antimatroid, the shelling antimatroid