Definitions
A set of points is defined to be 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.
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 definition, the intersection of all convex sets containing X is well-defined, and 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. 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, and therefore the sets given by these two definitions must be equal. In fact, according to Carathéodory's theorem, if X is a subset of an N-dimensional vector space, convex combinations of at most N + 1 points are sufficient in the definition above. Therefore, the convex hull of a set X of three or more points in the plane is the union of all the triangles determined by triples of points from X, and more generally in N-dimensional space the convex hull is the union of the simplices determined by at most N + 1 vertices from X.
If the convex hull of X is a closed set (as happens, for instance, if X is a finite set or more generally a compact set), then it is the intersection of all closed half-spaces containing X. The hyperplane separation theorem proves that in this case, each point not in the convex hull can be separated from the convex hull by a half-space. However, there exist convex sets, and convex hulls of sets, that cannot be represented in this way. One example is an open halfspace together with a single point on its boundary.
More abstractly, the convex-hull operator Conv has the characteristic properties of a closure operator:
- It is extensive, meaning that the convex hull of every set X is a superset of X.
- It is non-decreasing, meaning that, for every two sets X and Y with X ⊆ Y, the convex hull of X is a subset of the convex hull of Y.
- It is idempotent, meaning that for every X, the convex hull of the convex hull of X is the same as the convex hull of X.
Read more about this topic: Convex Hull
Famous quotes containing the word definitions:
“Lord Byron is an exceedingly interesting person, and as such is it not to be regretted that he is a slave to the vilest and most vulgar prejudices, and as mad as the winds?
There have been many definitions of beauty in art. What is it? Beauty is what the untrained eyes consider abominable.”
—Edmond De Goncourt (18221896)
“What I do not like about our definitions of genius is that there is in them nothing of the day of judgment, nothing of resounding through eternity and nothing of the footsteps of the Almighty.”
—G.C. (Georg Christoph)
“The loosening, for some people, of rigid role definitions for men and women has shown that dads can be great at calming babiesif they take the time and make the effort to learn how. Its that time and effort that not only teaches the dad how to calm the babies, but also turns him into a parent, just as the time and effort the mother puts into the babies turns her into a parent.”
—Pamela Patrick Novotny (20th century)