1

Assume we have $d+1$ vertices in $\mathbb{R}^d$. (We may assume they are affinely independent if necessary.) This post shows that the convex hull $C$ of these $d+1$ vertices is equal to the intersection of all half-spaces containing them. I am wondering is it true that $C$ is the intersection of $d+1$ half-spaces.

If those vertices are affinely independent, then we can linearly transform the convex hull to a standard $d$-simplex, which is determined by $d+1$ many dimension $d-1$ faces?

And it seems "affinely independence" is necessary?

RobPratt
  • 45,619
Connor
  • 2,023
  • If for example you points are all on a line (and d is at least 3) the convex hull is not the intersection of $d+1$ half spaces so you do need some independence condition. – quarague Jun 28 '22 at 11:46
  • An ordinary octohedron has 6 vertices and 8 faces. – kimchi lover Jun 28 '22 at 14:53

1 Answers1

1

While passing between vertices and half-spaces is easy in the affinely independent case, it get a lot more complicated in general.

For $d+1$ affinely independent points in a $d$-dimensional real affine space, there is one half-space for every vertex: the $d$ other vertices define an affine hyperplane, and the vertex itself chooses one of the two half-spaces separated by that hyperplane.

However if in $3$-dimensional space one glues together two regular tetrahedra along one triangle, the result is a convex polytope that is clearly the convex hull of its $5$ vertices, but which has $6$ faces so it also clearly needs at least $6$ half-spaces to define it as their intersection. If you embed this in a $4$-dimensional space (so the polytope has lower dimension than the space) then you need two more half-spaces in the intersection to cut out the embedded $3$-dimensional subspace (but the polytope is still the convex hull of $5$ points).

Also the ordinary cube shows that is it possible to have fewer half-spaces than vertices.

Marc van Leeuwen
  • 115,048