We’ve seen so far constructing a subdivision via lifting. But now we will construct this subdivision recursively. Let \(F\) be a face and suppose \(\mathbf v\notin\operatorname{aff}(F)\), then by Section 3.1,

Definition
The pyramid over \(F\) with apex \(\mathbf v\) is defined by $$ \begin{align*} \mathbf v*F := \operatorname{conv}\!\left(\{\mathbf v\}\cup F\right). \end{align*} $$

The pyramid is obtained by adjoining the vertex \(\mathbf v\) to every point of \(F\). For example, if \(F\) was a vertex, then \(v * F\) is an edge. If \(F\) was an edge, then \(v * F\) is a triangle illustrated below

Observe that if a face \(F\) is visible from \(\mathbf v\), then the pyramid \(\mathbf v*F\) lies outside the polytope \(P'\). Since \(F\) is visible from \(\mathbf v\), every segment joining \(\mathbf v\) to a point of \(F\) meets \(P'\) only at its endpoint on \(F\). Consequently, the pyramid extends outward from the boundary of \(P'\) and does not pass through the interior of \(P'\). This will be key to the the beneath-and-beyond construction: only the visible faces of the subdivision are joined to the new vertex but first, the following lemma:

Lemma 5.3.2
Let \(\mathcal S\) be a polyhedral complex and let \(\mathbf v \notin |\mathcal S|\). If, for every point \(\mathbf p\in |\mathcal S|\), the segment \([\mathbf v,\mathbf p]\) meets \(|\mathcal S|\) only in the point \(\mathbf p\), then $$ \begin{align*} \mathbf v * \mathcal S := \{\mathbf v * F : F\in\mathcal S\}\cup\mathcal S \end{align*} $$ is a polyhedral complex.

The line segment \([\mathbf v, \mathbf p]\) meets \(|\mathcal S|\) only at \(\mathbf p\) means \(v\) has an unobstructed view of the complex \(\mathcal{S}\). Then, we can construct a pyramid \(v * F\) for each face \(F\) in the complex \(\mathcal{S}\).

The claim is that the collection of these pyramids along with \(\mathcal{S}\) itself is a polyhedral complex.

Proof.

Fix a face \(F\in\mathcal S\). We first claim that \(\mathbf v\notin\operatorname{aff}(F)\). Suppose, for the sake of contradiction, that \(\mathbf v\in\operatorname{aff}(F)\). Let \(\mathbf p\in F^\circ\) be a point in the relative interior of \(F\). Since both \(\mathbf v\) and \(\mathbf p\) lie in the affine hull of \(F\), the segment \([\mathbf v,\mathbf p]\) is contained in \(\operatorname{aff}(F)\). Now, since \(\mathbf p\) is a relative interior point of \(F\), then there exists a neighborhood of \(\mathbf p\) inside \(\operatorname{aff}(F)\) that is contained in \(F\). This implies that a portion of the segment \([\mathbf v,\mathbf p]\) (closest to \(p\)) lies in \(F\). Hence, \([\mathbf v,\mathbf p]\cap F\) contains a nontrivial line segment, rather than just the single point \(\mathbf p\). But since \(F\subseteq |\mathcal S|\), then \([\mathbf v,\mathbf p]\cap |\mathcal S|\) is a segment rather than just the point \(\mathbf p\) itself which is a contradiction to the assumption that every segment \([\mathbf v,\mathbf p]\) meets \(|\mathcal S|\) only at \(\mathbf p\). Therefore, \(\mathbf v\notin\operatorname{aff}(F).\) Hence,

$$ \begin{align*} \mathbf v*F=\operatorname{conv}(\{\mathbf v\}\cup F) \end{align*} $$

is a well-defined pyramid with apex \(\mathbf v\) and base \(F\). Next, by Exercise 3.40 (TODO), every face of \(\mathbf v * F\) is either a face of \(F\) or a pyramid over a face of \(F\). Hence \(\mathbf v * F\) satisfies the containment property.

For the intersection property, suppose that \(F, G \in \mathbf v * \mathcal S\). We want to show that \(F \cap G\) is a common face of both \(F\) and \(G\). So suppose that \(F^{\circ} \cap G^{\circ}\) contains a point \(p\). If \(F, G\) are both cells of \(\mathcal{S}\), then that just implies \(F = G\) and there is nothing to prove. Hence, suppose that \(F = \mathbf v * F'\) for some \(F' \in \mathcal{S}\). Since \(\mathbf p \in F^{\circ}\), then \(p\) is in the relative interior of the pyramid \(\mathbf v * F'\). Now consider the ray starting at \(\mathbf v\) and passing through \(p\) so

$$ \begin{align*} \{ \mathbf v + t(\mathbf p - \mathbf v) \mid t \geq 0 \}. \end{align*} $$

Since \(\mathbf p\) is in the relative interior, then the ray meets \(F'\) at a unique point \(\mathbf p'\). Moreover, we claim that

$$ \begin{align*} \mathbf p'\in (F')^\circ. \end{align*} $$

Suppose, for the sake of contradiction, that \(\mathbf p'\notin (F')^\circ\). Then \(\mathbf p'\) lies on the boundary of the base \(F'\). Hence the segment \([\mathbf v,\mathbf p']\) is contained in the boundary of the pyramid \(\mathbf v * \mathbf F'\). But \(\mathbf p\) is also in \([\mathbf v,\mathbf p']\), so \(\mathbf p \in \partial(\mathbf v * F')\). However, \(\mathbf p\in F^\circ=(\mathbf v*F')^\circ\), so \(\mathbf p\) is an interior point of the pyramid. This is a contradiction. Therefore, \(\mathbf p' \in(F')^\circ\). Now we have two cases

  • Suppose that \(G\in\mathcal S\). Since \(\mathbf p\in G^\circ\), the ray from \(\mathbf v\) through \(\mathbf p\) meets \(G\) in the point \(\mathbf p'\). Hence \(\mathbf p'\in G^\circ\). Since we have already shown that \(\mathbf p'\in(F')^\circ\), it follows that \(\mathbf p'\in(F')^\circ\cap G^\circ\). Every point of \(|\mathcal S|\) lies in the relative interior of a unique cell of \(\mathcal S\). Therefore, \(F'=G\). Hence \(G\) is the base of the pyramid \(F=\mathbf v*F'\), and therefore \(G\) is a face of \(F\). Thus \(G\) is a common face of both \(F\) and \(G\).
  • Suppose that \(G=\mathbf v*G'\) for some \(G'\in\mathcal S\). The ray from \(\mathbf v\) through \(\mathbf p\) also meets the base \(G'\) in the point \(\mathbf p'\). Hence \(\mathbf p'\in(F')^\circ\cap(G')^\circ\). If \(F'\neq G'\), then the segment \([\mathbf v,\mathbf p']\) meets two distinct cells of \(\mathcal S\) in their relative interiors, contradicting the hypothesis of the lemma. Therefore, \(F'=G'\), and hence \(F=\mathbf v*F'=\mathbf v*G'=G\). Thus \(F\) is a common face of both \(F\) and \(G\).

This proves the intersection property. Therefore, \(v * \mathcal{S}\) is a polyhedral complex. \(\ \blacksquare\)

Theorem 5.3.3
Let \(\mathcal S'\) be a subdivision of the polytope \(P' \subseteq \mathbb{R}^d\), and let \(\mathbf v \in \mathbb{R}^d \setminus P'\). Then $$ \begin{align*} \mathcal S := \mathcal S' \cup \left( \mathbf v * \operatorname{Vis}_{\mathbf v}(\mathcal S') \right) \end{align*} $$ is a subdivision of \(P=\operatorname{conv}\bigl(\{\mathbf v\}\cup P'\bigr).\)

So if we have a subdivision \(\mathcal S'\) of a polytope \(P'\) and we have a vertex \(v \not\in P'\). Then the union of

  • the pyramids made of apex \(v\) and the visible faces from \(\mathbf v\) in \(\mathcal S'\)
  • and the faces in \(S'\)

is a subdivision of \(P = \operatorname{conv}(v) \cup P'\). To show this, we need to show \(\mathcal S\) is a polyhedral complex and that \(|S| = P\).

Proof

We first want to show that \(\mathcal S' \cup \left( \mathbf v * \operatorname{Vis}_{\mathbf v}(\mathcal S') \right)\) is a polyhedral complex. We know that \(\mathcal{S}'\) is a polyhedral complex. Moreover, by Lemma 5.3.2, \(\mathbf v * \operatorname{Vis}_{\mathbf v}(\mathcal S')\) is a polyhedral complex. It remains to show that these two polyhedral complexes intersect in a common subcomplex. We claim that

$$ \begin{align*} (\mathbf v * \operatorname{Vis}_{\mathbf v}(\mathcal S')) \cap \mathcal S' = \operatorname{Vis}_{\mathbf v}(\mathcal S'). \end{align*} $$

First observe that

$$ \begin{align*} \mathbf v * \operatorname{Vis}_{\mathbf v}(\mathcal S') &= \{ \mathbf v * F \mid F \in \operatorname{Vis}_{\mathbf v}(\mathcal S') \} \\ &= \{ \mathbf v * F \mid \mathbf v\notin T_F(\mathcal S') \}. \end{align*} $$

is a collection of pyramids whose bases are the visible faces from \(v\) in \(\mathcal S'\). Let \(F\in\operatorname{Vis}_{\mathbf v}(\mathcal S')\). Since \(\mathbf v\notin P'\), the apex of the pyramid \(\mathbf v*F\) does not lie in the affine hull of \(P'\). Therefore, the only part of the pyramid contained in \(P'\) is its base. Hence

$$ \begin{align*} (\mathbf v*F)\cap P'=F. \end{align*} $$

Taking the union over all visible faces \(F \in \operatorname{Vis}_{\mathbf v}(\mathcal{S}')\), we obtain

$$ \begin{align*} \left(\mathbf v * \operatorname{Vis}_{\mathbf v}(\mathcal S')\right) \cap \mathcal S' = \operatorname{Vis}_{\mathbf v}(\mathcal S'). \end{align*} $$

It remains to show that \(|\mathcal S| = P\). Since every cell of \(\mathcal S'\) is contained in \(P'\) and every pyramid \(\mathbf v*F\) is contained in \(\operatorname{conv}(\{\mathbf v\}\cup P')=P\), we have \(|\mathcal S| \subseteq P.\) Thus it remains to prove \(P \subseteq |\mathcal{S}|\). Let \(\mathbf p\in P\). If \(\mathbf p\in P'\), then \(\mathbf p\in|\mathcal S'|\subseteq|\mathcal S|\). Now suppose that \(\mathbf p\notin P'\). Consider the ray

$$ \begin{align*} \{\mathbf v+\lambda(\mathbf p-\mathbf v)\mid \lambda\ge0\}. \end{align*} $$

Since \(\mathbf p\in\operatorname{conv}(\{\mathbf v\}\cup P')\), this ray intersects \(P'\) in a unique point \(\mathbf p'\)….. [TODO]

So this gives an algorithm for triangulation by starting with a simplex \(P_0\) and then adding the remaining vertices one at a time by coning over the visible faces. By Exercise 5.19, the triangulation constructed is regular.

References