jenerated

Steinitz' theorem

$\DeclareMathOperator{\conv}{conv}$ $\DeclareMathOperator{\interior}{int}$ $\DeclareMathOperator{\relint}{relint}$ $\DeclareMathOperator{\isect}{\cap}$ $\DeclareMathOperator{\union}{\cup}$ I think convex geometry is kinda neat. I originally meant to make rigorous and share a back-of-napkin proof of Steinitz's theorem that a friend had in turn shared with me, but school picked up and I forgot about this. It's been a long-standing annoyance of mine that a dismaying proportion of convex geometry proofs hid simple geometric ideas behind smoke and mirrors (and unenlightening algebraic manipulations). It also helps that I like sharing proofs that make me happy.

This entry has been sitting here as a draft for over a year now (since September 4 of last year!), though. In its current state, it's not particularly rigorous, and it doesn't include the pictures I meant to draw, but whatever.

I did a quick google for Steinitz' theorem earlier today, only to discover that there is another theorem that goes by the same name that seems to be (considerably) better known to the internet. In the end, I had to grab Schneider to double-check the statement.

Loosely speaking, Steinitz's theorem tells us that given a point in the interior of a convex set, we can nest a convex polytope "strictly between" the point and the convex set. More formally,

Steinitz's theorem

Let $A \subset \mathbb{R}^n$ and $x \in \interior \conv A$. Then $x \in \interior \conv A'$ for some subset $A' \subset A$ with at most $2n$ points.

Caratheodory's theorem tells us that $x$ is a convex combination of at most $n+1$ points, but $x$ isn't necessarily in the interior of the convex hull of these $n+1$ points. We can, however, piggyback off this set of points to get another set of points that will satisfy Steinitz's theorem.

Let's look at that set of $n+1$ points that Caratheodory's theorem gives us. Say $S = \{x^0 x^1 \cdots x^{n}\} \subset A$ and $0 \leq \lambda_0, \cdots , \lambda_n < 1$ such that $\sum_{i=0}^n \lambda_i x^i = x$ and $\sum_{i=0}^n \lambda_i = 1$.

Below you will see that if $x \in \interior \conv S$, then we are done. If not, then $x$ must be on the boundary of $\conv S$. If we think of $\conv S$ as the intersection of some set of closed half-planes, then $x$ satisfies a subset of the inequalities associated with those hyperplanes with equality. (Note that for any polyhedron $T \subset \mathbb{R}^n$, $$x \in \interior \conv T$ is equivalent to saying that $x$ satisfies none of the hyperplane inequalities associated with $T$).

Let $I$ be that set of $\conv S$'s tight inequalities. There are two cases to consider.

1. $I$ is empty Then $x$ must lie in the interior of the convex hull of $S$.

2. $I$ is non-empty Then $x$ lies in the intersection of $|I|$ hyperplanes.

$x$ can be in the intersection of at most $n-1$ distinct hyperplanes of $\conv S$ (since each hyperplane after the first one brings the dimension of the intersection down).

Let $H$ be the hyperplane corresponding to an inequality of $I$. There exists a point $y$ such that the line segment $\{tx + (1-t)y\}$ is contained in $H \isect A$ that does not contain any elements of $H$ other than $x$. Observe that $x \in \relint \conv S \union \{y\}$. Essentially what's happening is that we're adding a little protrusion to $\conv S$ to get another polyhedron whose set of tight inequalities is $I$ minus the inequality that corresponded to $H$.

Repeat until there are no more active inequalities. The result is a polyhedron whose interior contains $x$.

At the end of the process, there are at most $n-1$ points added to $S$, so we have $x$ in the interior of a polyhedron that is the convex hull of at most $(n+1) + (n-1) = 2n$ points.