In these notes we describe that if we are given a polytope \(P = \operatorname{conv}(V)\) and any weight function \(\omega: V \rightarrow \mathbb{R}\), the lifting construction which we will describe below, produces a regular subdivision of \(P\).

Definition (Graph of \(\omega\))
Let \(V\subseteq \mathbb{R}^d\) be a finite set and let \(P = \operatorname{conv}(V)\). Let \(\omega: V\to\mathbb{R}\) be a function. The graph of \(\omega\) is $$ \begin{align*} V^{\omega} = \{ (v, \omega(v)) \in \mathbb{R}^{d+1} \mid v \in V \}. \end{align*} $$

For example if \(V = \{(0,0),(1,2),(1,4)\}\) and

$$ \begin{align*} \omega((0,0))=1, \omega((1,2))=2, \omega((1,4))=3. \end{align*} $$

Then

$$ \begin{align*} V^{\omega} = \{(0,0,1),(1,2,2),(1,4,3)\} \end{align*} $$

Now define

$$ \begin{align*} \uparrow_{\mathbb{R}} := \{(0,0,\cdots,t) \in \mathbb{R}^{d+1} \mid t \ge 0\}. \end{align*} $$

Then if \(p=(1,2,2)\),

$$ \begin{align*} p + \uparrow_{\mathbb{R}} = \{(1,2,2+t) \mid t \ge 0\} \end{align*} $$

is a vertical ray starting at \(p\) and going upward along the \(z\)-axis or going upward in the direction of the last coordinate axis. Now, define the coordinate projection

$$ \begin{align*} \pi:\mathbb{R}^{d+1} &\to \mathbb{R}^d \\ \pi(x_1,\ldots,x_d,x_{d+1}) &= (x_1,\ldots,x_d). \end{align*} $$

Note that \(\pi(\uparrow_{\mathbb{R}}) = \{0\}\). Finally, define

Definition (Epigraph)
The convex epigraph of \(\omega\) as $$ \begin{align*} E^\omega(V) := \operatorname{conv}(V^\omega) + \uparrow_{\mathbb{R}}. \tag{1} \end{align*}

So if \(V^{\omega} = \{(0,0,1),(1,2,2),(1,4,3)\}\), then we will take the convex hull of these points and then from each point \(p\) in the convex hull we will include all the points along the ray starting at \(p\) and going up along the \(z\)-axis. So \(E^w(V)\) consists of the convex hull together with everything lying directly above it. So we end up with figure 5.3 from the textbook.

Recall by Theorem 3.2.5 (Minkowski-Weyl), that a set \(Q\) is a polyhedron if and only if there exists a polytope \(P\) and a finitely generated cone \(C\) such that \(Q = P + C\). We know \(V^{\omega}\) is finite. Hence its convex hull is a polytope. Moreover, \(\uparrow_{\mathbb{R}}\) is a finitely generated cone. Hence \(E^\omega(V)\) defined in (1) is a polyhedron.

Proposition 5.1.4
Proposition 5.1.4. Fix a finite set \(V \subset \mathbb{R}^d\) and a hyperplane $$ H = \left\{ (\mathbf{x},x_{d+1})\in \mathbb{R}^{d+1} \mid \langle \mathbf{a},\mathbf{x}\rangle + a_{d+1}x_{d+1}=b \right \}. $$ If \(E^\omega(V)\subseteq H^{\le}\), then \(a_{d+1}\le 0\). If \(H\) is a supporting hyperplane, then the face \(F=E^\omega(V)\cap H\) is bounded if and only if \(a_{d+1}<0\).

Proof

Let \(\mathbf{p} = (\mathbf{q}, q_{d+1}) \in E^{\omega}(V)\) and recall that \(E^\omega(V)=\operatorname{conv}(V^\omega)+\uparrow_{\mathbb R}\). Thus,

$$ \begin{align*} \mathbf{p}+\uparrow_{\mathbb R}\subseteq E^\omega(V). \end{align*} $$

This implies that for every \(t\ge 0\),

$$ \begin{align*} (\mathbf{q},q_{d+1}+t)\in E^\omega(V). \end{align*} $$

In other words, once a point lies in \(E^\omega(V)\), then every point directly above it also lies in \(E^\omega(V)\). Now, suppose that \(E^{\omega}(V) \subset H^{\le}\) and recall that

$$ \begin{align*} H = \left\{ (\mathbf{x},x_{d+1})\in \mathbb{R}^{d+1} \mid \langle \mathbf{a},\mathbf{x}\rangle + a_{d+1}x_{d+1}=b \right \}. \end{align*} $$

Then by definition, we must have

$$ \begin{align*} \langle \mathbf{a},\mathbf{q}\rangle +a_{d+1}(q_{d+1}+t) \le b \end{align*} $$

for all \(t\ge 0\). Equivalently,

$$ \begin{align*} \langle \mathbf{a}, \mathbf{q}\rangle + a_{d+1}q_{d+1} + a_{d+1}t \le b \end{align*} $$

for all \(t\ge 0\). Note that \(\langle \mathbf{a}, \mathbf{q}\rangle + a_{d+1}q_{d+1}\) is a constant once \(\mathbf{q}\) is fixed. The only term that changes with \(t\) is \(a_{d+1}t\). Hence for the inequality to hold as \(t \to \infty\), we must have \(a_{d+1}\le 0\).

Now suppose that \(H\) is a supporting hyperplane, so

$$ \begin{align*} F=E^\omega(V)\cap H \tag{1} \end{align*} $$

is a nonempty face. We have already shown that \(a_{d+1} \leq 0\). Hence it suffices to show that \(F\) is unbounded if and only if \(a_{d+1} = 0\). We first claim that

$$ \begin{align*} a_{d+1} = 0 \quad \Longleftrightarrow \quad F + \uparrow_{\mathbb{R}} \subseteq F \tag{2} \end{align*} $$

Suppose \(F + \uparrow_{\mathbb{R}} \subseteq F\). Take any point \((\mathbf{q},q_{d+1}) \in F\). By (1), we know that \(F \subseteq H\). Hence

$$ \begin{align*} \langle \mathbf{a}, \mathbf{q}\rangle + a_{d+1}q_{d+1} = b. \tag{3} \end{align*} $$

Since \((\mathbf q,q_{d+1})\in F\) and \(F + \uparrow_{\mathbb{R}} \subseteq F\), then

$$ \begin{align*} \langle \mathbf{a}, \mathbf{q}\rangle + a_{d+1}(q_{d+1}+t) = b. \tag{4} \end{align*} $$

Subtracting (3) from (4) gives

$$ \begin{align*} a_{d+1}t = 0. \end{align*} $$

for every \(t \geq 0\). But this implies that \(a_{d+1} = 0\). Conversely, suppose that \(a_{d+1} = 0\). Take any point \((\mathbf q,q_{d+1})\in F.\) Since \(F\subseteq H\), then by definition

$$ \begin{align*} \langle\mathbf a,\mathbf q\rangle + a_{d+1}q_{d+1} &= b. \end{align*} $$

Now let \(t\ge0\). Then

$$ \begin{align*} \langle\mathbf a,\mathbf q\rangle +a_{d+1}(q_{d+1}+t) &= \langle\mathbf a,\mathbf q\rangle +0\cdot(q_{d+1}+t) \\ &= \langle\mathbf a,\mathbf q\rangle \\ &= b, \end{align*} $$

which implies that \((\mathbf q,q_{d+1}+t)\in H\). Now recall that \(F = E^\omega(V) \cap H\). So since \((\mathbf q,q_{d+1})\in F\), then it must be that

$$ \begin{align*} (\mathbf q,q_{d+1})\in E^\omega(V), \end{align*} $$

Since \(E^\omega(V)=\operatorname{conv}(V^\omega)+\uparrow_{\mathbb R}\), we showed earlier that every point directly above a point in \(E^\omega(V)\) also lies in \(E^\omega(V)\). Hence

$$ \begin{align*} (\mathbf q,q_{d+1}+t)\in E^\omega(V). \end{align*} $$

Therefore,

$$ \begin{align*} (\mathbf q,q_{d+1}+t)\in E^\omega(V)\cap H=F. \end{align*} $$

Since this holds for every (t\ge0), it follows that \(F+\uparrow_{\mathbb R}\subseteq F\). It remains to show that

$$ \begin{align*} \quad F + \uparrow_{\mathbb{R}} \subseteq F \quad \Longleftrightarrow \quad \text{F is unbounded} \tag{5} \end{align*} $$

First, suppose that \(F+\uparrow_{\mathbb R}\subseteq F.\) Take any point \(p\in F\). Then \(p+\uparrow_{\mathbb R}\subseteq F\). But

$$ \begin{align*} p+\uparrow_{\mathbb R} = \{p+(0,\ldots,0,t) \mid t \ge 0\} \end{align*} $$

is an infinite ray. Hence (F) contains an infinite ray, so (F) is unbounded. Conversely, suppose that (F) is unbounded. Since

$$ \begin{align*} F\subseteq E^\omega(V) = \operatorname{conv}(V^\omega)+\uparrow_{\mathbb R}, \end{align*} $$

and \(\operatorname{conv}(V^\omega)\) is bounded, the only source of unboundedness in \(E^\omega(V)\) is the cone \(\uparrow_{\mathbb R}\). Hence the only unbounded direction of \(E^\omega(V)\) is the upward direction. Since \(F\subseteq E^\omega(V)\), every unbounded ray contained in \(F\) must also be an upward ray. Therefore,

$$ \begin{align*} F+\uparrow_{\mathbb R}\subseteq F. \end{align*} $$

Combining (2) and (5), we conclude that

$$ \begin{align*} F \text{ is bounded} \quad\Longleftrightarrow\quad a_{d+1} < 0.\ \blacksquare \end{align*} $$

Note that by the construction above we have \(\pi(E^{\omega}(V)) = P\). Also note that the weights given by \(\omega\) will determine what the projection will exactly look like. In the next theorem, we show that in particular, \(P\) is the image under \(\pi\) of the collection of the bounded faces of \(E^{\omega}(V))\) and that the projection is a subdivision of \(P\) with vertices in \(V\). This is illustrated in the textbook figure 5.4

Proposition 5.1.5
Let \(P=\operatorname{conv}(V)\) and let \(\omega:V\to\mathbb{R}\). Then $$ \begin{align*} \mathcal{S}^{\omega}(V) := \left\{ \pi(F) \mid F\in\Phi^{\mathrm{bnd}} \left( E^{\omega}(V) \right) \right\} \end{align*} $$ is a subdivision of \(P\) with vertices in \(V\). Moreover, \(\mathcal{S}^{\omega}(V) \cong \Phi^{\mathrm{bnd}} \left(E^{\omega}(V) \right)\) as posets.

So given some height function \(\omega\) if we lift the the polytope up one dimension using the height function and then project the lifted polytope down. Then the resulting pieces form a subdivision of the original polytope. To show this, we show that the properties of a subdivision hold. First, the subdivision covers every point of \(P\). Each projected face is a cell in the subdivision and finally the intersection of any two cells is common face. One important note here is that the bounded lower faces are what matters in the lifted polyhedron. Every point of \(P\) sees only the closest lower bounded face directly above it. The vertical walls or unbounded faces don’t contribute any new information to the subdivision, so we just ignore them.

Proof. Let \(P=\operatorname{conv}(V)\) and \(\omega:V\to\mathbb{R}\). Let

$$ \begin{align*} \mathcal{S}^{\omega}(V) = \left\{ \pi(F) \mid F\in\Phi^{\mathrm{bnd}} \left (E^{\omega}(V) \right) \right\}. \end{align*} $$

To show that \(\mathcal{S}^{\omega}(V)\) is a subdivision of \(P\), we first show that every point of \(P\) lies in the projection of at least one bounded face of \(E^{\omega}(V)\). So let \(\mathbf{p} \in P\) be a point in \(P\). Since \(P = \pi \left(E^{\omega}(V)\right)\), there exists at least one point of \(E^{\omega}(V)\) whose projection is \(\mathbf{p}\). Moreover, since \(E^{\omega}(V)\) is an epigraph, the vertical line through \(\mathbf{p}\) intersects \(E^{\omega}(V)\) in a ray. Hence there is a unique smallest height above \(\mathbf{p}\) at which this vertical line first meets \(E^{\omega}(V)\). Define

$$ \begin{align*} \overline{\omega}(\mathbf{p}) := \min\{ h \in \mathbb{R} \mid (\mathbf{p},h) \in E^{\omega}(V) \}. \end{align*} $$

Let \(\widehat{\mathbf{p}} = \bigl(\mathbf{p}, \overline{\omega}(\mathbf{p}) \bigr)\). By construction, \(\widehat{\mathbf{p}}\in E^{\omega}(V)\) and is the lowest point of \(E^{\omega}(V)\) lying above \(\mathbf{p}\). Hence \(\widehat{\mathbf{p}}\) lies on the boundary of \(E^{\omega}(V)\). By Lemma 3.3.8, every point of a polyhedron lies in the relative interior of a unique face. Hence there exists a unique face \(F\preceq E^{\omega}(V)\) such that \(\widehat{\mathbf{p}}\in F^{\circ}\).

Next, we claim that \(F\) is bounded. Suppose, for the sake of contradiction, that \(F\) is unbounded. Then Proposition 5.1.4 implies that \(F+\uparrow_{\mathbb{R}}\subseteq F\). This implies that the vertical direction belongs to the affine hull of \(F\). Since \(\widehat{\mathbf p}\in F^\circ\), we can move a sufficiently small distance \(\epsilon>0\) in either direction along the vertical line while remaining in \(F^\circ\). Hence there exists \(\epsilon>0\) such that

$$ \begin{align*} (\mathbf{p},\overline{\omega}(\mathbf{p})-\epsilon)\in F^\circ\subseteq E^\omega(V). \end{align*} $$

This contradicts the definition of \(\overline{\omega}(\mathbf{p})\) as the smallest height for which \((\mathbf{p},\overline{\omega}(\mathbf{p}))\in E^\omega(V)\). Therefore \(F\) is bounded and every point \(\mathbf{p} \in P\) lies in the projection of some bounded face.

Next, we show that for every bounded face \(F\) of \(E^{\omega}(V)\), the restriction \(\pi|_{F^\circ} : F^\circ \to \mathbb{R}^d\) is injective. Since we have already shown that for each \(\mathbf{p}\in P\) there is a unique height \(h\) such that \((\mathbf{p},h)\) is contained in a bounded face of \(E^{\omega}(V)\), it suffices to prove that \(\pi\) is injective when restricted to the relative interior of a bounded face. By Proposition 5.1.4, there exists a supporting hyperplane

$$ \begin{align*} H = \left\{ (\mathbf{x},x_{d+1})\in\mathbb{R}^{d+1} \mid \langle\mathbf{a},\mathbf{x}\rangle-x_{d+1}=b \right\} \end{align*} $$

such that \(F=E^\omega(V)\cap H.\) Now define the map

$$ \begin{align*} s:\mathbb{R}^d &\to H \\ s(\mathbf{x}) &= (\mathbf{x},\langle\mathbf{a},\mathbf{x}\rangle-b). \end{align*} $$

We claim that \(s\) is the inverse of the restriction \(\pi|_H:H\to\mathbb{R}^d\). Indeed, for any \(\mathbf{x}\in\mathbb{R}^d\),

$$ \begin{align*} (\pi|_H\circ s)(\mathbf{x}) = \pi(\mathbf{x},\langle\mathbf{a},\mathbf{x}\rangle-b) = \mathbf{x}. \end{align*} $$

Conversely, let \((\mathbf{x},x_{d+1})\in H\). Since \(\langle\mathbf{a},\mathbf{x}\rangle-x_{d+1}=b\), we have \(x_{d+1}=\langle\mathbf{a},\mathbf{x}\rangle-b\). Hence

$$ \begin{align*} (s\circ\pi|_H)(\mathbf{x},x_{d+1}) = s(\mathbf{x}) = (\mathbf{x},\langle\mathbf{a},\mathbf{x}\rangle-b) = (\mathbf{x},x_{d+1}). \end{align*} $$

Therefore \(s=(\pi|_H)^{-1}\), so \(\pi|_H\) is an isomorphism. Since \(F^\circ\subseteq H\), it follows that the restriction \(\pi|_{F^\circ}:F^\circ\to\mathbb{R}^d\) is injective.

Finally, since every point of \(P\) lies in the projection of some bounded face of \(E^\omega(V)\), the projected bounded faces cover \(P\). Moreover, we have shown that for every bounded face \(F\), the restriction \(\pi|_{F^\circ}:F^\circ\to\mathbb{R}^d\) is injective. Hence each bounded face projects isomorphically onto its image, preserving its face structure. Therefore the collection

$$ \begin{align*} \mathcal{S}^{\omega}(V) = \left\{ \pi(F) \mid F\in\Phi^{\mathrm{bnd}}\!\left(E^{\omega}(V)\right) \right\} \end{align*} $$

forms a subdivision of \(P\). \(\ \blacksquare\)

References