convex_hull - note-math

[affine_space]

The affine space of a finite-dimensional vector space is origin selection + coordinate/vector space

where and are set-theoretically isomorphic, both isomorphic to

Using addition to represent the position after traveling unit time along vector starting from origin :

Using subtraction to represent the vector between two points : corresponds to the unique such that

The affine space allows changing the origin. When origin , coordinates

Affine subspace is equivalent to origin + vector subspace

Example Parameterization of a 2D subspace in 3D :

[affine_combination]

Affine combination of points

is a well-defined affine point, meaning the coordinate definition does not depend on the choice of origin. Let the coordinates of be , then the coordinates of point are . If we change the origin , then the coordinates of point will also be translated by along with the origin

Intuition for affine combination: the simplest example is proportional points on a line determined by two points

Nested affine combinations can be used

For example, the linear combination of points with the additional restriction forms a triangle

It can be considered as , where

is the affine combination of , representing the side of the triangle formed by ,

The nesting is denoted as , and this operation should be associative

[affine_coordinate] The in the point can be considered as a kind of coordinate based on the points . Called affine coordinates. alias barycentric coordinates [barycentric_coordinate]

Example [center_of_affine_point_set] Midpoint/centroid of affine combination has affine coordinates

[affine_independent]

Affine independent := For each , vertex is not in the affine combination of , i.e.

This means each point in the affine combination is not redundant. Intuitively, is not in the affine subspace spanned by

Affine dependent := There exists , vertex is in the affine combination of , i.e.

This means there exists a point among the affine combination points that is redundant. Intuitively, is in the affine subspace spanned by

Affine independent <==> After selecting one point e.g. as origin, are linearly independent

If vertices are affine independent, any affine combination point has a unique coordinate representation

In particular, the unique coordinates of point are

An -dimensional affine space has at most affinely independent points. This matches the count of origin + vectors numerically

If instead of , although the coordinate does not change with origin change, it is not an affine point

[affine_map_point_ver] alias [simplicial_map] Affine map := A map taking points of another affine space as vertices to points , for non-vertex cases

Affine map <==> After choosing origins for two affine spaces, for the two linear spaces, linear map + translation

Note that linear maps and translations do not commute. Example: in

Rotate by degrees first to get , then translate by to get
Translate by first to get , then rotate by degrees to get

[convex_hull] := the affine combination of with the additional restriction

[simplex] := convex hull formed by affinely independent points

[extreme_point_of_convex_hull]

Sometimes, among the points generating a convex hull, some points are redundant (note the restriction ), they can be generated by other points. Extreme points are those that cannot be generated by other points

Prop Extreme points already generate the original convex hull, and are the minimal generating set

Proof Continuously eliminate redundant points from and . Extreme points belong to the convex hull and cannot be generated by other points, only by themselves, so they are necessary for generating the convex hull

Prop The extremum of an affine function with domain and codomain can be attained at extreme points

Proof

Suppose the extremum is attained at

is generated by extreme points

Define the extremum of function values at extreme points

is affine, so

Thus . Hence the extremum can attain the extreme value at the extreme point

Let finite-dimensional real affine space and its vector space

Def := interval of := convex hull generated by

Def := open interval := convex hull generated by , with the additional condition

Def [convex] convex set :=

Prop Intersection of convex sets is convex

The following references ref-34

Def [core] Similar to topological interior.

Prop [finite_intersect_preserve_core] . Proof is obvious. uses

Def [linearly_accessible] Similar to topological closure.

Prop

let convex

Prop let . then . Corollary:

Proof

let . let

We need to show

Need to show there exists such that

Since , there exists such that

Since is convex, . Let to conclude

Prop [core_open_interval_core] let , let . then

Proof

If then reduce to previous prop

Since , there exists such that

let . For , there exist such that

Since is convex, , therefore

Since this holds for all , there exists a slightly larger such that

Since , by the previous proposition, , thus

Prop convex ==> convex

Proof Follows from previous propositions

Prop convex ==> convex

Proof

let . We need to show

According to the definition of linearly-accessible, there exist such that

By convexity,

Either , then

This implies there exists

Thus

Def [boundary]

Affine maps do not preserve boundaries. A simple counterexample is mapping a tetrahedron in to a rectangle in via an affine map determined by vertex correspondence

Prop Let , then satisfies for

Proof Otherwise, if there exists such that , then leading to a contradiction

Prop convex & ==>

Proof

is obvious

let

Take

let

Since , there exists such that

Thus

Therefore

Prop convex & ==>

Proof

is obvious

let

Then

Take . By the definition of ,

Note: It is possible that in but in an affine subspace of

Prop convex & ==>

Proof

Prop [finite_intersect_preserve_convex_closed]

Proof It is easy to see

Def convex open , convex closed

We can define convex hull for general sets

Def

Proof (of convex)

let

let . Consider

Sum of coefficients

If is convex then . In particular, for general ,

Def := the smallest dimension of an affine subspace containing

Prop [full_dim_iff_core_nonempty]

Proof core nonempty <==> can span linearly independent directions

Prop

Proof When number of points , they are affinely dependent, and there are redundant points

Prop [convex_of_union] Let be convex, then

Proof

Use block summation technique. For , consider

where

Prop Let be convex and . Then there exist convex such that (i.e., complements) and

Proof

Define a partial order on convex set pairs containing respectively and disjoint:

By maximal_linear_order_exists, take a maximal linearly ordered chain, take the union of the components of the pairs respectively, denote the result as

It is easy to prove . We also need to prove

Suppose

Obviously , by the maximality of in the partial order,

Take . Since , . By convex_of_union, , thus there exists such that

Similarly, take , , there exists such that

are three distinct points, forming a triangle. Within the triangle it is easy to prove . But , leading to , a contradiction

Let be convex and complements. Let

Prop

Proof

let

Since are disjoint, contradicts , contradicts

Thus and

Therefore and

Hence

Since are complements, , thus

Thus

Prop

Proof If or it is obvious. Assume . Define . Take the supremum of to get

Prop If , then is a hyperplane

Proof

is flat

Take . We need to show

Suppose there exists such that . Assume . Since , by core_open_interval_core, , contradicting
Take as origin. Take . Suppose , then , there exists and such that . If , replace with

Prop [hyperplane_separation] Hyperplane separation theorem. Let be convex and , then there exists a hyperplane separating

Note: Separation means , not strict separation

Prop separates

Def [support_hyperplane] Supporting hyperplane: lies on one side of hyperplane and

Prop If and then (i.e., ) Proof cannot be in , and

Prop let , let , then there exists a supporting hyperplane with

Proof Apply the hyperplane separation theorem to , because . Hence . Take , then , by contradiction we get , thus

Prop . Proof Proof by contradiction: take , using the definition of and the definition of separating hyperplane leads to a contradiction

Prop Affine subspace with and , let . Then there exists a supporting hyperplane of with

Proof Let . Let . Then . If , take . Then spans the one-dimensional complement of . But we have the following contradictions

The one-dimensional complement of is not

The following references ref-35

Def [order_of_boundary] The intersection of all supporting hyperplanes at is an affine subspace, the order is defined as its dimension

Def [vertex] Vertex := boundary point of order

Prop [bd_convex_hull_core] let . if , then

Prop [bd_convex_hull_bd] let . if , then

Proof is convex and so . if not then , hence , contradicting

The above two propositions can be generalized to (assuming are already extreme points of )

Prop [support_hyperplane_at_core_of_convex_bd_subset] Let be convex, let be the affine subspace spanned by , then any supporting hyperplane containing (core in ) satisfies , hence

Proof

Let . If , then , thus spans the complement space of , therefore

But and for sufficiently small near ,

contradicts

Prop

is possible. Consider the cube in . Consider . Consider . Then

Prop If there exists such that (this property is called is an exposed face) then and thus

Prop Duality between vector space hyperplanes and linear functionals. Vector space hyperplane <==> there exists a linear functional such that

Since , the subspace in the dual space of corresponds to the subspace of

Prop Duality between vector subspaces and subspaces of linear functionals. A -dimensional vector subspace of <==> an -dimensional vector subspace of . The direct connection is

Proof Choose a basis of . Then a basis of corresponds to

Prop . Proof

Prop The linear functionals corresponding to hyperplanes span an -dimensional subspace in <==> is a -dimensional subspace of

Prop is a vertex <==> there exist hyperplanes , the corresponding linear functionals are linearly independent, forming a basis of , and

Prop If , then , thus

Prop

Proof Let , then thus

Prop

Def Sum of subspaces

Prop Dimension of intersection of subspaces

Proof

where

is the composition of two embeddings . Similarly for

is surjective

satisfy the exact sequence property: injective, surjective,

By linear algebra

Therefore

Prop The two sides of an affine hyperplane are

Prop (Similarly for )

The following deals with the equivalence of two descriptions of polytopes

Convex hull of a finite set of points
Bounded intersection of half-spaces

Assume are already extreme points. Assume already span ; otherwise, work in the lower-dimensional affine subspace they span.

Prop For each hyperplane not containing the origin, there exists a unique such that

Proof A vector space hyperplane corresponds to a one-dimensional space spanned by in

The equivalent equation is , where

[pole] In a coordinate system, can be expressed as , corresponding to

[polar_hyperplane] Conversely, in a coordinate system, gives the hyperplane

There is a one-to-one correspondence between

Affine hyperplanes not containing the origin

Prop

Proof

[polar_dual] let .

Prop

Proof

The definition of tells us that for

Hence

Prop If for every there exists a hyperplane with semi-strict separation , then and thus

Proof

We prove that if

But the definition of is

Let correspond to . In the “if” branch

Let correspond to . In the “then” branch

Thus

Prop If

is convex
(convex closed)

then for every there exists a hyperplane semi-strictly separating and

Proof

Take

Consider

For

By definition of core, there exists such that

has a supremum

. Since (convex closed), , thus , hence

There exists a hyperplane separating the convex set and the convex set

The line segment can be linearly extended into the interior of , so is not a subset of ; instead, lies in the direction of the complement space of

Thus semi-strictly separates and

Prop If then

Proof

let

Prop satisfies

convex
(convex closed)

Proof

For , let , with , with

Then

Choose sufficiently small so that

(convex closed)

==> there exists such that , i.e., for every ,

is composed of the union of simplices formed by taking points from :

The vertices of each simplex are affinely independent, and the line segment has a unique affine coordinate representation in it:

For a given , the solution set of these inequalities on forms a closed interval

Hence

is a closed interval in , hence the closure of also belongs to , thus belongs to some

also implies , thus

Therefore , thus (convex closed)

Prop

Proof

if , then

, then

Prop

Proof

Prop satisfies

convex
(convex closed)

Proof

. , choose sufficiently small
let .

i.e.,
This is a continuous function of with values in , let to get , hence

let convex, ,

Prop Let . Then is a supporting hyperplane of , supporting at the point , which is the polar-dual of the supporting hyperplane of at

Proof

By the definition of ,

Hence is a supporting hyperplane of , supporting at , and

Prop These are all possible supporting hyperplanes of

Proof

Let be a supporting hyperplane of , supporting at

Then is a supporting hyperplane of supporting at

Hence is a supporting hyperplane of , supporting at

Def A polytope generated as the convex hull of a finite set of points is called a V-polytope (Vertex). A polytope generated as a bounded intersection of half-spaces is called an H-polytope (Hyperplane)

Prop An H-polytope satisfies

convex
(convex closed)

Proof Each satisfies the above two conditions, and a finite intersection also satisfies them

Analogous to extreme points of V-polytopes, H-polytopes have extreme hyperplanes. For , if , then is redundant and can be removed.

[extreme_hyperplane] Def Extreme hyperplane := one that cannot be expressed as containing the region defined by the intersection of other half-spaces

Prop Extreme hyperplanes already generate the original H-polytope and are the minimal generating set

Proof Similar to extreme points, continuously eliminate redundant hyperplanes

Let the H-polytope have . Assume the are already extreme hyperplanes

Def [facet]

Prop A facet is an -dimensional H-polytope

Proof

For , or is an -dimensional affine subspace. So it’s easy to see that is also an H-polytope

We show that has nonempty core in

Define

. The proof uses

Because it’s an extreme hyperplane,

Hence there exists

Take , then

Therefore

The 1-dimensional and the -dimensional intersect at a point

is -dimensional, so can emit in all -dimensional directions, particularly in all directions within , thus , hence . Therefore is -dimensional

Prop (thus facets of an H-polytope are supporting hyperplanes)

Proof

Consider

Therefore

i.e.,

Def Recursively define the -faces of as the facets of the -faces of

Prop Recursively, -faces come from intersections of certain facets (-faces)

Def Two -faces are adjacent if their intersection is a -face

Prop Let . Then the intersection of all supporting hyperplanes of equals the intersection of all facets containing . Proof Facets span the extreme hyperplanes, so if a supporting hyperplane is not spanned by a facet, it is redundant

Def [extreme_point] An extreme point of a general convex set is defined as such that is convex

Prop and convex ==> . Proof ==> is not convex

Prop is an extreme point <==>

Prop Vertex ==> extreme point (for general convex set )

Proof

We prove non-extreme ==> non-vertex

Non-extreme ==> there exist such that

By core_open_interval_core,

By bd_convex_hull_bd,

By support_hyperplane_at_core_of_convex_bd_subset, , thus is not a vertex

Prop For an H-polytope , if , then lies in the core of some -face

Proof

By support_hyperplane_at_core_of_convex_bd_subset, if , then is not in the core of an -face, so it lies in a facet of an -face

Recursively, until lies in a facet of a -face, then could be in

the core of a -face, or
a facet of a -face

But the latter recursively gives

Prop The number of -faces is finite. In particular, the number of -faces, i.e., vertices, is finite

Prop For an H-polytope, vertices are exactly the extreme points

Proof

We prove that if is an extreme point, then it is a vertex. If it were not a vertex, then would lie in the core of some convex face with , and faces are subsets of , and , so would not be an extreme point

In general, extreme point does not imply vertex. Consider the parabola in . At , the only supporting hyperplane is , so , but is an extreme point

Prop For a V-polytope , we have

Proof

, so

Suppose , then , thus

Hence . Therefore

We have already assumed is an -dimensional region, but if it is of dimension , might not be bounded

Def [bounded] Bounded := The intersection of every line with is a bounded interval

Prop The endpoints of the bounded intersection interval lie in

Prop If bounded and (convex closed), then the intersection of a line with is a closed bounded interval

Assume is bounded and convex closed from now on

Prop

Proof Take , take a line containing , it intersects in a closed interval whose endpoints lie in

Prop An affine subspace of is convex closed. Proof Cases with dimension have been proven. For dimension , it is the intersection of convex closed sets, hence by finite_intersect_preserve_convex_closed, is also convex closed

Prop If there exists an affine subspace of such that , then in and in are the same, thus

Proof Obviously in implies in . Conversely, let be in in , then there exists such that , and since is convex closed, , hence belongs to in

Prop If , then the convex hull of in and in are the same

Prop in and in are the same, thus

Prop Let be a supporting hyperplane, then

Proof

let . Since are convex closed, is also convex closed, thus

Hence and

Need to show

let

If then

Then

Thus

Hence

The case is similar

If , then , and since , we have

Therefore

let

Since are convex closed, is also convex closed

Thus , so , hence

Need to show

let . Since and , we have

Thus

Prop Extreme points exist, i.e., , and

Proof

Induction on dimension. In one dimension, it is a closed bounded interval, extreme points are the endpoints

We have already proven and , so we only need to prove

Let . Take a supporting hyperplane of

is convex closed and bounded, thus is convex closed and bounded in . Moreover

, by induction,

However

Thus , hence

Prop Bounded H-polytope ==> V-polytope

Proof

Finite number of vertices ==> finite number of extreme points,

Bounded ==> extreme points generate , i.e.,

Prop -dimensional bounded H-polytope ==> -dimensional V-polytope

Prop If is a V-polytope, then is bounded

Proof

let

Since , has lower and upper bounds, as well as a supremum and infimum

Prop In spaces of dimension , if is a

line segment
ray
line

not passing through the origin, then its polar-dual is:

the intersection of two half-spaces defined by hyperplanes not passing through the origin
the intersection of a half-space defined by a hyperplane not passing through the origin and a half-space defined by a hyperplane passing through the origin
degenerate to dimension

Proof

Let . Then
Let

Expanding gives

For this inequality to hold for all , we need . And for , we need

is a half-space defined by a hyperplane not passing through the origin. is a half-space defined by a hyperplane passing through the origin
Let

For to hold for all , we need , which is an -dimensional hyperplane passing through the origin

Prop Let be an -dimensional V-polytope. Choose a point in as origin to establish a coordinate system. Then

the polar-dual is bounded, hence is a bounded H-polytope
contains the origin, hence by full_dim_iff_core_nonempty, is -dimensional

Proof

Let , then , thus .

is a line segment, ray, or line, but contains the origin, so forces to be the intersection of two half-spaces defined by hyperplanes not passing through the origin, hence is a line segment
and each contains the origin

Prop -dimensional V-polytope ==> -dimensional bounded H-polytope

Proof is an -dimensional V-polytope ==> Choose a point in as origin to establish a coordinate system. is an -dimensional bounded H-polytope and contains the origin ==> is an -dimensional V-polytope ==> is an -dimensional bounded H-polytope

Prop -dimensional V-polytope <==> -dimensional bounded H-polytope

Prop Let be a bounded polytope, let be an affine function, then is a bounded polytope. Proof Use V-polytope representation

Similar to the V-polytope case, the extremum of an -valued affine function can be attained at extreme points, according to

More generally, the maximum of a continuous convex function () or the minimum of a continuous concave function ( is convex) can be attained at extreme points