6
$\begingroup$

I have two sets, each of which is the convex hull of finitely many points in $\mathbb{R}^n$ (in my case $\mathbb{R}^5$, but that shouldn't really matter). I'm certain that their intersection is itself the convex hull of finitely many points.

This seems to be one of those things that's "obvious" but hard to prove. A (somewhat terse) proof in two dimensions is given by The intersection of finite number of convex hulls is a convex hull.

I am unsure whether the induction mentioned is to handle $\mathbb{R}^n$. Attempting to generalize the argument even to $\mathbb{R}^3$ or $\mathbb{R}^3$, let alone $\mathbb{R}^n$ gets messy fast. I'm wondering if there's an easier way to handle this.

One idea is to show that a set is the convex hull of finitely many points iff both it is bounded and it is the intersection of finitely many closed half-spaces. That could be simpler, but I'm not sure how to do that either.

$\endgroup$
1
  • $\begingroup$ Nice question. I agree, there should be an easy to remember and easy to communicate version of the plan you sketch in your last paragraph. $\endgroup$ Aug 21, 2019 at 4:07

2 Answers 2

4
$\begingroup$

In "Polytopes, Rings, and K-Theory," Bruns/Gubeladze attribute the following to Minkowski:

$P\subseteq \mathbb{R}^n$ is a polytope $\iff$ $P$ is the convex hull of a finite subset of $\mathbb{R}^n$

which is the theorem you reference as a proof method in your last paragraph.

Sidenote: In attempting to look this up, it seems to be a special case of what many call the "Weyl-Minkowski theorem", which Bruns/Gubeladze instead attribute to Motzkin, so the attributions might still be in conflict. In any case, it makes it hard to look up a reference.


If we've already proven the above theorem, then your question is rephrased as "Is the intersection of two polytopes itself a polytope?" The answer to this is obviously "yes," as the intersection of two bounded sets is bounded and intersecting an intersection of finitely many closed [affine] half-spaces with another intersection of finitely many closed [affine] half-spaces is trivially an intersection of finitely many closed [affine] half-spaces (which is a whole lot of a words to basically say "finite + finite = finite")


The problem then is in proving this theorem. Of course, Bruns/Gubeladze prove it in the above book, but they develop quite a few tools in the previous sections to make their proof succinct, so if you want to see their proof, I'll direct you to the book.

To prove it from first principles, the following sketch should work:

  • $(\Rightarrow)$ By definition, there is some positive integer $N$ and for any $1\leq i \leq N,\lambda_i \in \mathbb{R}^n, b_i \in \mathbb{R}$ such that $$P = \{x \in \mathbb{R}^n : \lambda_i \cdot x \leq b_i, \forall i\}$$ For any $J \subseteq \{1,\ldots,N\},$ define $F_J = P \cap \{x \in \mathbb{R}^n : \lambda_j\cdot x = b_j, \forall j \in J\},$ and let $V$ denote the set of $\subseteq$-minimal elements of $\Big\{F_J : J \subseteq \{1,\ldots,N\}\Big\}\setminus\{\emptyset\}.$ Using the assumption $P$ is bounded and every affine linear subspace of positive dimension is unbounded, we can show $V = \{\{x_1\}, \ldots, \{x_m\}\}$ is a set of singletons. Now consider the convex hull of these points, which is immediately a subset of $P$ itself. This leaves showing $P$ is a subset of the given convex hull, which is a little tedious, but probably would work best by induction, showing each $F_J$ is the convex hull of some subset of $V.$

  • $(\Leftarrow)$ Obviously the convex hull $P$ of a finite set $V$ is bounded, so we would need to show $P$ is a polyhedron. Toward this end, we may assume $V$ is minimal (if we remove any point, the convex hull will be strictly smaller), and since an affine subspace of $\mathbb{R}^n$ is the finite intersection of closed affine half-spaces (by the existence of an orthogonal basis) we may reduce to the case that the affine subspace spanned by $V$ is all of $\mathbb{R}^n.$ Now just note that there is an affine linear map taking the $(|V|-1)$-simplex onto the convex hull of $V.$

$\endgroup$
0
$\begingroup$

First, note that the image of a convex hull of a finite set under a linear (affine) map is also the convex hull of a finite set ( Hint: consider the images of the generators).

Consider now two finite sets of points $\{P_i\}_{1\le i\le k}$ and $\{Q_j\}_{1\le j\le l}$ in an affine space. Consider the set of points in $\mathbb{R}^{k+l}$ described by $$\begin{eqnarray} \sum \lambda_i P_i = \sum \mu_j Q_j \\ \sum \lambda_i = \sum \mu_j = 1 \\ \lambda_i, \mu_j \ge 0\\ \end{eqnarray}$$

It is easy to see that the intersection of the convex hulls is the image of this set under the map $$(\lambda_i, \mu_j) \mapsto \sum \lambda_i P_i$$

Now we finish by proving :

Let $m, n\ge 1$ natural numbers, $A \in M(\mathbb{R}, m\times n)$ a matrix of size $m \times n$ with real entries, $b \in \mathbb{R}^m$. Consider the subset of unit cube in $\mathbb{R}^n$ defined by $$\begin{eqnarray} A \cdot x = b \\ 0\le x_i \le 1 \end{eqnarray}$$

If the above set is not void then it is the convex hull of a finite subset of itself.

The proof is by induction on $n$. If $n=1$ it is easy. Assume true for all $n-1\ge 1$. If our subset has only one point, done. Otherwise, take a point $X$ and another one $Y$ in the set. The line $XY$ intersects the boundary of the cube in two points $X'$, $X''$ such that $X$ is in the segment $X'X''$. Now for each intersection of the set with a face of the we have the induction hypothesis ( it is basically a subset of $\mathbb{R}^{n-1}$, see also the observation at the very beginning of the proof). I say we are done.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .