Question

give a four-point example P that has both maximal point not on the convex hull and a convex hull point is not maximal

Answer 1

Introduction:

In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. 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. 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.

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 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.

As well as for finite point sets, 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.

Definitions:

A set of points in a Euclidean space 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

1. The (unique) minimal convex set containing X
2. The intersection of all convex sets containing X
3. The set of all convex combinations of points in X
4. The union of all simplices with vertices in X

For bounded sets in the Euclidean plane, not all on one 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 contract; when it becomes taut, it encloses the convex hull of S. This formulation does not immediately generalize to higher dimensions: for a finite set of points in three-dimensional space, a neighborhood of a spanning tree of the points encloses them with arbitrarily small surface area, smaller than the surface area of the convex hull. However, in higher dimensions, variants of the obstacle problem of finding a minimum-energy surface above a given shape can have the convex hull as their solution.

For objects in three dimensions, the first definition states that the convex hull is the smallest possible convex bounding volume of the objects. The definition using convex combinations may be extended from Euclidean spaces to arbitrary real vector spaces or affine spaces; convex hulls may also be generalized in a more abstract way, to oriented matroids

Upper and lower hulls:

In two dimensions, the convex hull is sometimes partitioned into two parts, the upper hull and the lower hull, stretching between the leftmost and rightmost points of the hull. More generally, for convex hulls in any dimension, one can partition the boundary of the hull into upward-facing points (points for which an upward ray is disjoint from the hull), downward-facing points, and extreme points. For three-dimensional hulls, the upward-facing and downward-facing parts of the boundary form topological disks.

Topological properties:

Closed and open hulls-

The closed convex hull of a set is the closure of the convex hull, and 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), then it equals the closed convex hull. However, an intersection of closed half-spaces is itself closed, so when a convex hull is not closed it cannot be represented in this way.

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 vertices of a square, regular octahedron, or higher-dimensional cross-polytope.

Topologically, the convex hull of an open set is always itself open, and the convex hull of a compact set is always itself compact. However, there exist closed sets for which the convex hull is not closed. For instance, the closed set

Extreme points and compact hulls:

An extreme point of a convex set is a point in the set that does not lie on a line segment between any other two points of the same set. For a convex hull, every extreme point must be part of the given set, because otherwise it cannot be formed as a convex combination of given points. According to the Krein–Milman theorem, 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. However, this may not be true for convex sets that are not compact; for instance, the whole Euclidean plane and the open unit ball are both convex, but neither one has any extreme points. Choquet theory extends this theory from finite convex combinations of extreme points to infinite combinations (integrals) in more general spaces.