1.1.1 Convex polyhedra, polytopes and cones

A convex polyhedron $P\subset \mathbb{R}^{d}$ is an intersection of a finite number of closed half-spaces. A bounded convex polyhedron is called a polytope; equivalently, a polytope is the convex hull of a finite number of points.

By $\operatorname{aff}(P)$ we denote the affine hull of $P$ , that is, the smallest affine subspace of $\mathbb{R}^{d}$ containing $P$ . The dimension of a convex polyhedron is the dimension of its affine hull.

A hyperplane $H$ is called a supporting hyperplane of a convex polyhedron $P$ if $H\cap P\neq \varnothing$ while $P$ lies in one of the closed half-spaces bounded by $H$ . The intersection $P\cap H$ is called a face of $P$ (sometimes it makes sense to consider $\varnothing$ and $P$ as faces of $P$ , too). Faces of dimension zero, one and $\dim P-1$ are called vertices, edges and facets, respectively. A $d$ -dimensional polytope is called simple if each of its vertices belongs to exactly $d$ facets (equivalently, to exactly $d$ edges).

A convex polyhedral cone is the intersection of a finite number of closed half-spaces whose boundary hyperplanes all pass through the origin. Equivalently, it is the positive hull

of a finite number of vectors. A cone is called pointed if it contains no linear subspaces, except for $\{0\}$ ; equivalently, if it has $\{0\}$ as a face. A cone $C$ is called simplicial if it is the positive hull of $k$ linearly independent vectors. In this case, the intersection of $C$ with an appropriately chosen hyperplane is a $(k-1)$ -simplex.

See [Reference Ewald10] or [Reference Ziegler46], for more details on polyhedra, cones and fans.

1.1.2 Normal fans and normally equivalent polyhedra

By $\unicode[STIX]{x1D6E5}^{(k)}$ we denote the collection of $k$ -dimensional cones of the fan $\unicode[STIX]{x1D6E5}$ . The support of a fan is the union of all of its cones: that is,

A fan $\unicode[STIX]{x1D6E5}$ is called complete if $\operatorname{supp}(\unicode[STIX]{x1D6E5})=\mathbb{R}^{d}$ and it is called pointed (respectively, simplicial) if all of its cones are pointed (respectively, simplicial). Complete simplicial fans in $\mathbb{R}^{d}$ are in one-to-one correspondence with geodesic triangulations of $\mathbb{S}^{d-1}$ .

For every proper face $F$ of a convex polyhedron $P$ there is a supporting hyperplane through $F$ . The set of outward normals to all such hyperplanes spans a convex polyhedral cone, namely, the normal cone at $F$ . Below is a more formal definition.

Note that Definition 1.2 makes sense also when $\dim P<d$ . In this case, every $N_{F}(P)$ contains the linear subspace $\operatorname{aff}(P)^{\bot }$ . The following are some simple facts about the normal fan.

• ∙ $\operatorname{supp}({\mathcal{N}}(P))$ is a convex polyhedral cone in $\mathbb{R}^{n}$ , positively spanned by the normals to the facets of $P$ .

• ∙ If $F$ is a face of $G$ , which is a face of $P$ , then $N_{G}(P)$ is a face of $N_{F}(P)$ .

• ∙ $\dim N_{F}(P)=d-\dim F$ .

• ∙ $P$ is a polytope $\Leftrightarrow {\mathcal{N}}(P)$ is complete.

• ∙ $\dim P=d\Leftrightarrow {\mathcal{N}}(P)$ is pointed.

• ∙ $P$ is a simple $d$ -polytope $\Leftrightarrow {\mathcal{N}}(P)$ is complete and simplicial.

The set $T(\unicode[STIX]{x1D6E5})$ is a cone in the sense that scaling a convex polyhedron does not change its normal fan. Later we will see that the closure of $T(\unicode[STIX]{x1D6E5})$ is, in fact, a convex polyhedral cone.

Not every fan $\unicode[STIX]{x1D6E5}$ is the normal fan of some convex polyhedron; examples are shown in Figure 13. If it is, that is, if $T(\unicode[STIX]{x1D6E5})\neq \varnothing$ , then $\unicode[STIX]{x1D6E5}$ is called polytopal.

Normally equivalent polyhedra are also called “analogous” [Reference Alexandrov1] or “strongly isomorphic” [Reference McMullen27, Reference McMullen30]. The term “normally equivalent” is used in [Reference De Loera, Rambau and Santos9].

1.1.3 Support numbers

Let $P\subset \mathbb{R}^{d}$ be a $d$ -dimensional convex polyhedron. Then one-dimensional cones of ${\mathcal{N}}(P)$ correspond to facets of $P$ . Denote by $V:=(v_{1},\ldots ,v_{n})$ the collection of unit vectors that generate ${\mathcal{N}}(P)^{(1)}$ and denote by $F_{i}$ the facet of $P$ with the outward unit normal $v_{i}$ . Then $P$ is the solution set of a system of linear inequalities $\langle v_{i},x\rangle \leqslant h_{i}$ , $i=1,\ldots ,n$ for some $h\in \mathbb{R}^{n}$ . We will express this as $P=P(V,h)$ , where

Here, by abuse of notation, $V$ denotes the $n\times d$ -matrix whose $i$ th row is  $v_{i}$ . By a repeated abuse of notation, we will also write $V={\mathcal{N}}(P)^{(1)}$ . Thus $V$ stands for any of the following objects:

• ∙ a collection of $n$ rays in $\mathbb{R}^{d}$ starting at the origin;

• ∙ a collection of $n$ unit vectors in $\mathbb{R}^{d}$ ; and

• ∙ an $n\times d$ -matrix with rows of norm one.

From $\Vert v_{i}\Vert =1$ , it follows that $h_{i}$ is the signed distance from the coordinate origin to the affine hull of $F_{i}$ (see Figure 2). The numbers $h_{i}$ are called the support numbers of the polyhedron $P$ and $h=(h_{1},\ldots ,h_{n})\in \mathbb{R}^{n}$ is the support vector of  $P$ .

Figure 2

Support numbers: $h_{i}>0$ , $h_{j}<0$ .

For any pointed polytopal fan $\unicode[STIX]{x1D6E5}$ , the support vector determines an embedding

where $V=\unicode[STIX]{x1D6E5}^{(1)}$ . Due to

the equivalence classes modulo translation correspond to points in $\mathbb{R}^{n}/\operatorname{im}V$ . Thus

and $\widetilde{T}(\unicode[STIX]{x1D6E5})=\unicode[STIX]{x1D70B}^{-1}(T(\unicode[STIX]{x1D6E5}))$ , where

is the canonical projection.

1.1.4 Support function

In particular, if $P$ is a polytope, then $h_{P}$ is defined on the whole $\mathbb{R}^{d}$ .

The support function is positively homogeneous and convex: that is, $h_{P}(\unicode[STIX]{x1D706}v)=\unicode[STIX]{x1D706}h_{P}(v)$ for $\unicode[STIX]{x1D706}>0$ and

for all $\unicode[STIX]{x1D706}\in [0,1]$ , $v,w\in \operatorname{supp}({\mathcal{N}}(P))$ . The support function can be defined for any closed convex set and there is a one-to-one correspondence between closed convex sets and positively homogeneous convex functions defined on a convex cone in $\mathbb{R}^{d}$ .

The formula in Lemma 1.5 implies that the linearity domains of $h_{P}$ are the normal cones at the vertices of $P$ ; that is, the nonlinearity locus of $h_{P}$ is the union of the normal cones at the edges of $P$ .

Note that if $\unicode[STIX]{x1D6E5}$ is not simplicial, then $\widetilde{h_{\unicode[STIX]{x1D6E5}}}$ is not defined for all $h$ .

Let $P=P(V,h)$ be a $d$ -dimensional convex polyhedron such that ${\mathcal{N}}(P)^{(1)}=V$ . Since $h_{P}(v_{i})=h_{i}$ ,

1.1.5 Fans refinement and the Minkowski sum

Indeed, let $h\in \widetilde{T}(\unicode[STIX]{x1D6E5})\subset \mathbb{R}^{n}$ . Choose a generic $y\in \mathbb{R}^{n}$ and consider $h^{\prime }=h\,+\,ty$ with $t$ sufficiently small. The extension $\widetilde{h_{\unicode[STIX]{x1D6E5}}^{\prime }}$ is not defined, but it becomes so if every $\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}$ is appropriately subdivided (by a convex hull construction). This yields a simplicial fan $\unicode[STIX]{x1D6E5}^{\prime }$ such that $\widetilde{h_{\unicode[STIX]{x1D6E5}^{\prime }}^{\prime }}$ is convex, (the convexity across $\unicode[STIX]{x1D6E5}^{(d-1)}$ is preserved for small $t$ ). As for the second statement of the lemma, by choosing $h\in \widetilde{T}(\unicode[STIX]{x1D6E5})$ and $y\in \widetilde{T}(\unicode[STIX]{x1D6E5}^{\prime })$ we see, in a similar way, that $h+ty\in \widetilde{T}(\unicode[STIX]{x1D6E5}^{\prime })$ for all $t>0$ .

The geometric picture behind this argument is that translating facets of a non-simple polyhedron generically and by small amounts makes the polyhedron simple without destroying any of its faces.

The additive structure on the space of support vectors is related to the Minkowski addition. However, one should be careful when the summands are not normally equivalent.

Fix $V$ and define $P(h):=P(V,h)$ . Lemma 1.13 implies that, in general,

because $P(h)+P(h^{\prime })$ can have more facets than $P(h+h^{\prime })$ . See Figure 3, which shows fragments of three-dimensional polyhedra. (However, $P(h+h^{\prime })\supset P(h)+P(h^{\prime })$ always holds.)

Figure 3

Minkowski addition does not always correspond to the addition of support numbers.

Instead, we have the following.

Also, clearly, $h_{\unicode[STIX]{x1D706}K}=\unicode[STIX]{x1D706}h_{K}$ and $P(\unicode[STIX]{x1D706}h)=\unicode[STIX]{x1D706}P(h)$ for $\unicode[STIX]{x1D706}>0$ . This is false for $\unicode[STIX]{x1D706}<0$ . Taking differences of the support functions embeds the space of convex polytopes in the vector space of the so-called virtual polytopes (see [Reference McMullen29, Reference Pukhlikov and Khovanskiĭ36]).

A subset of a Euclidean space is called relatively open, if it is open as a subset of its affine hull. For example, an open half-line in $\mathbb{R}^{2}$ is relatively open.

The convexity follows from

for ${\mathcal{N}}(P(h))\simeq {\mathcal{N}}(P(h^{\prime }))$ and $\unicode[STIX]{x1D706}\in [0,1]$ , and the relative openness follows from

for $\unicode[STIX]{x1D700}$ sufficiently small, whether positive or negative.

1.1.6 Linear inequalities describing a type cone

Let $P\subset \mathbb{R}^{d}$ be a $d$ -polytope with the normal fan $\unicode[STIX]{x1D6E5}$ . Then $P=P(h)$ for $h\in \widetilde{T}(\unicode[STIX]{x1D6E5})$ (we omit $V=\unicode[STIX]{x1D6E5}^{(1)}$ from the notation $P(V,h)$ ). For every cone $\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}$ let $F_{\unicode[STIX]{x1D70E}}(h)$ be the face of $P(h)$ with the normal cone $\unicode[STIX]{x1D70E}$ .

If $\unicode[STIX]{x1D70E}\in \unicode[STIX]{x1D6E5}^{(d-1)}$ , then $F_{\unicode[STIX]{x1D70E}}(h)$ is an edge; denote its length by

Of course, all functions $\ell _{\unicode[STIX]{x1D70E}}^{\unicode[STIX]{x1D6E5}}:\widetilde{T}(\unicode[STIX]{x1D6E5})\rightarrow \mathbb{R}$ descend through $\unicode[STIX]{x1D70B}:\mathbb{R}^{n}\rightarrow \mathbb{R}^{n}/\operatorname{im}V$ to functions on $T(\unicode[STIX]{x1D6E5})$ . However, the proofs of the lemmas in this section are better written in terms of $h$ than $\unicode[STIX]{x1D70B}(h)$ . Due to the fact that $T(\unicode[STIX]{x1D6E5})=\unicode[STIX]{x1D70B}(\widetilde{T}(\unicode[STIX]{x1D6E5}))$ , the statements of the lemmas are easily translated in terms of $T(\unicode[STIX]{x1D6E5})$ .

Note that if $\unicode[STIX]{x1D6E5}$ is not simplicial, then we might have several different choices for $v_{i_{\unicode[STIX]{x1D6FC}}}$ , $v_{j_{\unicode[STIX]{x1D6FD}}}$ in the proof of Lemma 1.17, and hence several formulas for $\ell _{\unicode[STIX]{x1D70E}}^{\unicode[STIX]{x1D6E5}}$ in terms of $h_{i}$ . This is due to the fact that, for a non-simplicial $\unicode[STIX]{x1D6E5}$ , the set $\widetilde{T}(\unicode[STIX]{x1D6E5})$ does not span the space $\mathbb{R}^{n}$ of support vectors. Thus different linear functions on $\mathbb{R}^{n}$ have the same restrictions to $\operatorname{span}(\widetilde{T}(\unicode[STIX]{x1D6E5}))$ .

Note that the function $\ell _{\unicode[STIX]{x1D70E}}^{\unicode[STIX]{x1D6E5}}(h)$ is well defined only on $\operatorname{span}(\widetilde{T}(\unicode[STIX]{x1D6E5}))$ . Due to Lemma 1.19, the above description of $\widetilde{T}(\unicode[STIX]{x1D6E5})$ in the non-simplicial case is unambiguous.

1.2.1 The compatibility and the irredundancy domains

As in §1.1.3, for an $h\in \mathbb{R}^{n}$ , denote by $P(h)$ the solution set of the system $Vx\leqslant h$ . It can happen that the set $P(h)$ is empty; and even when it is non-empty, it can happen that some of the inequalities $\langle v_{i},x\rangle \leqslant h_{i}$ can be removed without changing $P(h)$ . This leads us to consider the two subsets of $\mathbb{R}^{n}$

that is, all those $h$ for which $P(h)\neq \varnothing$ and

where irredundant means that removing any inequality from the system makes the solution set bigger.

As in the case with a type cone and a lifted type cone, equation (2) implies that both $\widetilde{\operatorname{co}}(V)$ and $\widetilde{\operatorname{ir}}(V)$ are invariant under translation by $Vt$ for any $t\in \mathbb{R}^{d}$ . Therefore it suffices to study their quotients under the map

For every polytopal fan $\unicode[STIX]{x1D6E5}$ with $\unicode[STIX]{x1D6E5}^{(1)}=V$ , $T(\unicode[STIX]{x1D6E5})\subset \operatorname{ir}(V)$ and we will see later that these types of cone decompose the interior of $\operatorname{ir}(V)$ . Moreover, this can be extended to a subdivision of $\operatorname{co}(V)$ , the so-called secondary fan.

Most of the material presented here can be found in [Reference Billera, Filliman and Sturmfels5, Reference Billera, Gel’fand and Sturmfels6, Reference De Loera, Rambau and Santos9, Reference McMullen27, Reference McMullen28]. The notation $\operatorname{ir}$ was introduced in [Reference McMullen27], meaning “inner region”, but, in some later works by the same author, the terminology was changed to the “irredundancy domain”.

1.2.2 Gale duality, linear dependencies and evaluations

For the moment, we do not require all $v_{i}$ to have norm one (in fact, we even allow $v_{i}=0$ or $v_{i}=v_{j}$ for $i\neq j$ ).

Indeed, the uniqueness up to a linear transformation follows from the freedom in the choice of the isomorphism $\mathbb{R}^{n}/\operatorname{im}V\cong \mathbb{R}^{n-d}$ . The involutivity of the Gale transform follows by transposing the short exact sequence in Definition 1.23. It allows us to also call the vector configuration $(\bar{v}_{i})$ Gale dual to $(v_{i})$ .

As an immediate consequence of Definition 1.23,

The elements of $\ker V^{\top }$ are the linear dependencies between the vectors $(v_{1},\ldots ,v_{n})$

while the elements of $\operatorname{im}\bar{V}$ are the evaluations of linear functionals on $(\bar{v}_{1},\ldots ,\bar{v}_{n})$

Therefore (7) can be phrased as “dependencies of $V$ equal evaluations on  $\bar{V}$ ”. Of course, the same holds with $V$ and $\bar{V}$ exchanged.

In the next lemma, the rank of a vector configuration means the dimension of its linear span, so that a rank $d$ configuration is the same as a linearly spanning configuration. We also use the notation $[n]:=\{1,\ldots ,n\}$ and, for any subset $I\subset [n]$ , we denote by $V_{I}$ the vector configuration $(v_{i}\mid i\in I)$ .

Let $V\in \mathbb{R}^{n\times d}$ be a vector configuration such that its Gale diagram $(\bar{v}_{1},\ldots ,\bar{v}_{n})$ contains no zero vectors (a necessary and sufficient condition for this is given in part 3 of Lemma 1.26). The affine Gale diagram is constructed by choosing an affine hyperplane $A\subset \mathbb{R}^{n-d}$ non-parallel to each of $\bar{v}_{i}$ and scaling each $\bar{v}_{i}$ so that

In addition, a point $\bar{p}_{i}$ is colored black if $\unicode[STIX]{x1D6FC}_{i}>0$ and white if $\unicode[STIX]{x1D6FC}_{i}<0$ .

An affine Gale diagram determines the vector configuration $V$ up to independent positive scalings of $v_{i}$ . Indeed, the point $\bar{p}_{i}$ , together with its color, determines $\bar{v}_{i}$ up to a positive scaling; and positive scaling $\bar{v}_{i}\mapsto \unicode[STIX]{x1D6FD}_{i}\bar{v}_{i}$ of $\bar{V}$ corresponds to positive scaling $v_{i}\mapsto \unicode[STIX]{x1D6FD}_{i}^{-1}v_{i}$ of $V$ .

For more details on Gale duality, see [Reference De Loera, Rambau and Santos9, Reference Ewald10, Reference Ziegler46].

1.2.3 Positive circuits and $\operatorname{co}(V)$

An inclusion-minimal linearly dependent set is one that is linearly dependent, while each of its proper subsets is not.

The minimality condition implies that a linear dependence $\unicode[STIX]{x1D706}^{C}\subset \mathbb{R}^{C}$ between vectors of a circuit $C$ is unique up to a scaling and that all coefficients $\unicode[STIX]{x1D706}_{i}^{C}$ are non-zero. In particular, it makes sense to speak about the signs of the coefficients (up to a simultaneous change of all signs).

A circuit $C$ is called positive if all coefficients of the corresponding linear dependence can be chosen to be positive: that is, if

By the dependence-evaluation duality (7), to a positive circuit $C$ there corresponds a linear functional $\unicode[STIX]{x1D707}^{C}\in \mathbb{R}^{n-d}$ such that

Namely, $\unicode[STIX]{x1D706}^{C}=\bar{V}\unicode[STIX]{x1D707}^{C}$ . Since $\bar{V}$ has full rank, $\unicode[STIX]{x1D707}^{C}$ is well defined up to a scaling. In addition, the minimality of $C$ implies that $\bar{V}_{[n]\setminus C}$ is a maximal non-spanning subconfiguration of $\bar{V}$ . Such subconfigurations are called cocircuits. Thus

(See also the second part of Lemma 1.26.)

Note that if $\operatorname{pos}(V)$ is pointed, then $V$ has no positive circuits, and hence the description (9d) yields $\operatorname{co}(V)=\mathbb{R}^{n-d}$ . This is in full accordance with the dualization of the last statement of the theorem: $\bar{V}$ is positively spanning if and only if $\operatorname{pos}(v_{1},\ldots ,v_{n})$ is pointed.

1.2.4 Hyperbolic circuits and $\operatorname{ir}(V)$

From now on, we assume that $v_{i}\neq 0$ and $v_{i}\neq \unicode[STIX]{x1D706}v_{j}$ for $\unicode[STIX]{x1D706}>0$ .

Our main goal here is to prove an analog of Theorem 1.30 for the space $\operatorname{ir}(V)$ . For this, we need some preliminary work.

Recall that $P(h)=\{x\in \mathbb{R}^{d}\mid Vx\leqslant h\}$ and that $h\in \widetilde{\operatorname{co}}(V)\Leftrightarrow P(h)\neq \varnothing$ . Define

Life becomes easier if we restrict our attention either to the interior $\operatorname{int}\operatorname{ir}(V)$ or to the closure $\operatorname{clir}(V)$ of the irredundancy domain. Note that they are the images under the map (6) of the interior and of the closure of $\widetilde{\operatorname{ir}}(V)$ , respectively.

The proof is similar to that of the last part of Lemma 1.34: $v_{i}\in F_{i}(\mathbf{1})$ and, since $\langle v_{i},v_{j}\rangle <1$ , $\dim F_{i}(\mathbf{1})=d-1$ . The polytope $P(\mathbf{1})$ is circumscribed about the unit sphere. Its normal fan is related to the Delaunay tessellation (see §4.2).

Note that the assumption $\Vert v_{i}\Vert =1$ is not too restrictive: scaling all vectors $v_{i}$ by positive factors scales the support numbers $h_{i}$ correspondingly. In the context of Gale duality, if $v_{i}$ is replaced by $\unicode[STIX]{x1D706}_{i}v_{i}$ , then it suffices to replace $\bar{v}_{i}$ by $\unicode[STIX]{x1D706}_{i}^{-1}\bar{v}_{i}$ .

Two more definitions will be needed.

(The $k$ -core is also called the set of vectors of depth $k$ ; see [Reference Wagner45].)

If $w_{i}\neq 0$ for all $i$ , then the $1$ -core is the positive hull

Similarly, the $2$ -core can be expressed as

For example, if, for every $w_{i}$ ,there is a $j\neq i$ such that $w_{j}=w_{i}$ , then $\operatorname{core}_{2}(W)=\operatorname{core}_{1}(W)=\operatorname{pos}(W)$ .

A hyperbolic circuit of cardinality two consists of two non-zero vectors $v_{i}$ and $v_{j}$ such that $v_{i}=\unicode[STIX]{x1D706}v_{j}$ for $\unicode[STIX]{x1D706}>0$ . In this case, any of the indices $i$ and $j$ can be declared to be $p(C)$ . As we assumed at the beginning of this section that $v_{i}\neq \unicode[STIX]{x1D706}v_{j}$ for $\unicode[STIX]{x1D706}>0$ , every hyperbolic circuit has cardinality at least three, and thus the positive index $p(C)$ is well defined.

Equation (11) means that we are scaling the coefficients of every hyperbolic circuit $C$ so that

Due to the dependence-evaluation duality (see (26) and the two equations following it), to every hyperbolic circuit there corresponds a unique vector $\unicode[STIX]{x1D707}^{C}\in \mathbb{R}^{n-d}$ such that

1.2.5 Chambers and type cones

Let $V=(v_{1},\ldots ,v_{n})$ be a positively spanning configuration of $n$ different unit vectors in $\mathbb{R}^{d}$ . By results of the previous sections, every polytope $P(h)$ with outer facet normals $v_{i}$ is represented by a point $y=\unicode[STIX]{x1D70B}(h)\in \mathbb{R}^{n-d}$ lying in the interior of the $2$ -core of the Gale dual configuration $\bar{V}=(\bar{v}_{1},\ldots ,\bar{v}_{n})$ . We now want to describe how the relative position of $y$ with respect to $\bar{v}_{i}$ determines the combinatorics of the polytope.

By slightly modifying the notation, we will distinguish between the geometric normal fan ${\mathcal{N}}(P(h))$ and the abstract fan $\unicode[STIX]{x1D6E5}$ isomorphic to ${\mathcal{N}}(P(h))$ . Here $\unicode[STIX]{x1D6E5}$ is a collection of subsets of $[n]$ such that

where, as usual, $V_{\unicode[STIX]{x1D70E}}=\{v_{i}\mid i\in \unicode[STIX]{x1D70E}\}$ .

Lemma 1.40 allows us to give a very concise description of the type cones of the vector configuration $V$ .

Equivalently, a relatively open chamber is an inclusion-minimal intersection of relative interiors of cones generated by $W$ and the chamber fan is the coarsest common refinement of all cones $\operatorname{pos}(W_{I})$ , $I\subset [n]$ .

Indeed, two points $y_{1},y_{2}\in \mathbb{R}^{n-d}$ belong to the same type cone if and only if the corresponding polytopes have the same normal fan. By Lemma 1.40, this is equivalent to $y_{1}$ and $y_{2}$ belonging to the same collections of relatively open cones $\operatorname{pos}(\bar{V}_{I})$ . Since relatively open and closed cones are related through the $\cup$ and $\setminus$ operations, this is equivalent to $y_{1}$ and $y_{2}$ belonging to the same collections of closed cones.

Note that if the fan $\unicode[STIX]{x1D6E5}$ is simplicial, then $|\unicode[STIX]{x1D70C}|=d$ for all $\unicode[STIX]{x1D70C}\in \unicode[STIX]{x1D6E5}^{(d)}$ , and hence $|[n]\setminus \unicode[STIX]{x1D70C}|=n-d$ . According to Lemma 1.26, the vector configuration $\bar{V}_{[n]\setminus \unicode[STIX]{x1D70C}}$ is linearly independent, so that (15) represents $T(\unicode[STIX]{x1D6E5})$ as a finite intersection of open simplicial $d$ -cones.

Chambers outside $\operatorname{int}\operatorname{ir}(V)$ can be studied using the operations of contraction and deletion on vector configurations. It is easy to see that, as a Gale dual of $V_{[n]\setminus i}$ (configuration obtained by deletion), one can take projections of vectors of $\bar{V}_{[n]\setminus i}$ along $\bar{v}_{i}$ (configuration obtained by contraction). According to that, the type cones $T(\unicode[STIX]{x1D6E5})$ with $\unicode[STIX]{x1D6E5}^{(1)}$ generated by $V_{[n]\setminus i}$ are the chambers of the contracted Gale dual $\bar{V}_{[n]\setminus i}$ . The contraction can be seen as a central projection in $\mathbb{R}^{n-d}$ from $\bar{v}_{i}$ . This projection maps those chambers of $\operatorname{Ch}(\bar{V})\cap \unicode[STIX]{x2202}\operatorname{clir}(V)$ visible from $\bar{v}_{i}$ to the chambers of $\operatorname{Ch}(\bar{V}_{[n]\setminus i})\cap \operatorname{clir}(V_{[n]\setminus i})$ .

Chambers on the boundary of $\operatorname{co}(V)$ correspond to type cones of polytopes of dimension smaller than $d$ . The facet normals of such a polytope $P$ are obtained from $V$ by contraction along vectors $v_{i}$ orthogonal to $\operatorname{aff}(P)$ .

1.2.6 Facets of $\operatorname{clir}(V)$ and truncated polytopes

Recall that $C\subset [n]$ is a circuit of $V$ if and only if $[n]\setminus C$ is a cocircuit of $\bar{V}$ : that is, the index set of a maximal non-spanning subconfiguration. This subconfiguration spans a hyperplane which is the kernel of the linear functional $\unicode[STIX]{x1D707}^{C}$ (see the beginning of §1.2.3).

By (12d), every facet of $\operatorname{clir}(V)=\operatorname{core}_{2}(\bar{V})$ is determined by a positive or a hyperbolic circuit of $V$ . The corresponding hyperplane in $\mathbb{R}^{n-d}$ spanned by $\bar{V}_{[n]\setminus C}$ has all of $\bar{V}_{C}$ on one of its sides, if $C$ is positive, and separates $\bar{v}_{p(C)}$ from $\bar{V}_{C^{-}}$ , if $C$ is hyperbolic.

Although every facet corresponds to a cocircuit, not every cocircuit (not even every hyperbolic one) corresponds to a facet of $\operatorname{core}_{2}(\bar{V})$ , as the following example shows.

In the next example, every positive and every hyperbolic cocircuit determines a facet of the $2$ -core.

Figure 6

A fragment of the $2$ -core of the vertices of the dodecahedron.

Note that $P\cap \{x\in \mathbb{R}^{d}\mid \langle v,x\rangle =h_{P}(v)\}=F$ . Thus, geometrically, truncation means pushing a supporting hyperplane of $P$ at $F$ inwards. The operation of truncating an edge of a $3$ -polytope is shown in Figure 7.

Figure 7

Truncating an edge of a $3$ -polytope.

For any positive or hyperbolic circuit $C$ of $V$ , define

1.3.1 Parallelepipeds with fixed face directions

Let $(v_{1},v_{2},v_{3})$ be a basis of $\mathbb{R}^{3}$ , put $v_{i+3}=-v_{i}$ , $i=1,2,3$ and consider the resulting configuration $V$ of six vectors in $\mathbb{R}^{3}$ .

All polyhedra with facet normals $V$ are normally equivalent: they are parallelepipeds with face normals $\pm v_{i}$ . The normal fan $\unicode[STIX]{x1D6E5}$ is generated by a hyperplane arrangement spanned on the vectors $v_{1},v_{2},v_{3}$ .

The lifted type cone $\widetilde{T}(\unicode[STIX]{x1D6E5})$ consists of $h\in \mathbb{R}^{6}$ that satisfy

By identifying $\mathbb{R}^{6}/\operatorname{im}V$ with $\{h\in \mathbb{R}^{6}\mid h_{4}=h_{5}=h_{6}=0\}$ , we obtain

The extreme rays of $\operatorname{cl}T(\unicode[STIX]{x1D6E5})$ correspond to degeneration of a parallelepiped into a segment parallel to one of the vectors $v_{1}\times v_{2}$ , $v_{2}\times v_{3}$ , $v_{3}\times v_{1}$ .

The Gale diagram of $V$ has the property $\bar{v}_{i+3}=\bar{v}_{i}$ , $i=1,2,3$ . This fits together with the fact that $\operatorname{co}(V)=\operatorname{ir}(V)$ : the second core of a vector configuration where each vector is repeated twice is its convex hull (see Definition 1.36 and equation (12b)). The facets of the cone (19) correspond to the three positive circuits $\{1,4\}$ , $\{2,5\}$ and $\{3,6\}$ .

1.3.2 Polygons

Let $\unicode[STIX]{x1D6FC}:=(\unicode[STIX]{x1D6FC}_{1},\ldots ,\unicode[STIX]{x1D6FC}_{n})$ with $0<\unicode[STIX]{x1D6FC}_{i}<\unicode[STIX]{x1D70B}$ be an $n$ -tuple of real numbers such that $\sum _{i}\unicode[STIX]{x1D6FC}_{i}=2\unicode[STIX]{x1D70B}$ . Let $v_{1},\ldots ,v_{n}\in \mathbb{R}^{2}$ be unit vectors such that the angle from $v_{i}$ to $v_{i+1}$ equals $\unicode[STIX]{x1D6FC}_{i+1}$ (of course, the indices are taken modulo $n$ ). This determines a fan $\unicode[STIX]{x1D6E5}$ in $\mathbb{R}^{2}$ . The fan is polytopal since, for every collection of positive numbers $a_{1},\ldots ,a_{n}$ such that $\sum _{i=1}^{n}a_{i}v_{i}=0$ , there is a convex polygon with edge lengths $a_{i}$ and edge normals $v_{i}$ . We will denote $T(\unicode[STIX]{x1D6E5})$ by $T(\unicode[STIX]{x1D6FC})$ . Note that $\operatorname{cl}T(\unicode[STIX]{x1D6FC})$ is a pointed $(n-2)$ -dimensional cone. To avoid dealing with trivial cases, below, we assume that $n\geqslant 5$ .

By Lemma 1.21, every facet of $T(\unicode[STIX]{x1D6FC})$ corresponds to vanishing of an edge: $\ell _{i}=0$ . This is possible without making any other edges disappear if and only if $\unicode[STIX]{x1D6FC}_{i}+\unicode[STIX]{x1D6FC}_{i+1}\leqslant \unicode[STIX]{x1D70B}$ . It follows that $\operatorname{cl}T(\unicode[STIX]{x1D6FC})$ has $n$ , $n-1$ or $n-2$ facets. Denote by $T_{i}$ the facet $\ell _{i}=0$ of $\operatorname{cl}T(\unicode[STIX]{x1D6FC})$ . If $j\notin \{i,i-1,i+1\}$ , then $T_{i}$ and $T_{j}$ meet along a codimension two facet. Otherwise, $T_{i}$ and $T_{i+1}$ meet if and only if $\unicode[STIX]{x1D6FC}_{i}+\unicode[STIX]{x1D6FC}_{i+1}+\unicode[STIX]{x1D6FC}_{i+2}<\unicode[STIX]{x1D70B}$ .

An extreme ray $e$ of $\operatorname{cl}T(\unicode[STIX]{x1D6FC})$ corresponds to triangles with fixed edge normals $v_{i_{1}},v_{i_{2}},v_{i_{3}}$ . This means that $\ell _{j}=0$ for all $j\notin \{i_{1},i_{2},i_{3}\}$ while $\ell _{i_{\unicode[STIX]{x1D6FC}}}\neq 0$ . Thus $e$ is contained in exactly $n-3$ facets, and hence $T(\unicode[STIX]{x1D6FC})$ is simple. It follows that $\operatorname{cl}T(\unicode[STIX]{x1D6FC})$ is the cone over an $(n-3)$ -dimensional polytope that is either a simplex, a truncated simplex or a doubly truncated simplex. See  [Reference Bavard and Ghys4] for more details and the case of non-convex polygons.

In the Gale diagrams language, the cone $\operatorname{cl}T(\unicode[STIX]{x1D6FC})$ is the 2-core of $\bar{V}$ . Figure 5 shows an example for $n=5$ , where this cone has three facets.

1.3.3 Polygonal prisms

Embed $\mathbb{R}^{2}$ in $\mathbb{R}^{3}$ and add to the vectors $v_{1},\ldots ,v_{n}\in \mathbb{R}^{2}$ from the preceding example the third basis vector and its inverse: $v_{n+1}=e_{3}$ and $v_{n+2}=-e_{3}$ . The new vector configuration $V^{+}$ determines only one pointed fan, namely, the normal fan of a prism over an $n$ -gon. Denote this fan by $\unicode[STIX]{x1D6E5}^{+}$ and denote its type cone by $T^{+}(\unicode[STIX]{x1D6FC})$ . Then

Thus $T^{+}(\unicode[STIX]{x1D6FC})$ is a product of $T(\unicode[STIX]{x1D6FC})$ with a half-space. It follows that

The new extreme ray $\{0\}\times \mathbb{R}^{+}$ corresponds to degeneration of the prism into a segment parallel to $e_{3}$ .

The Gale diagram of $V^{+}$ lives in the space $\mathbb{R}^{n-1}$ , which is one dimension higher than $\bar{V}$ . It is easy to see that $\bar{V^{+}}$ is obtained from $\bar{V}$ by adding two equal vectors $\bar{v}_{n+1}=\bar{v}_{n+2}=e_{n-1}$ . It follows that the 2-core of $\bar{V}\cup \{e_{n-1},e_{n-1}\}$ is the pyramid over the 2-core of $\bar{V}$ , which yields the same result as above.

1.3.4 Triangular bipyramid

Let $u_{1},u_{2},u_{3}\in \mathbb{R}^{2}$ be outward unit normals to the edges of a regular triangle. Choose $\unicode[STIX]{x1D706},\unicode[STIX]{x1D707}>0$ such that $\unicode[STIX]{x1D706}^{2}+\unicode[STIX]{x1D707}^{2}=1$ and consider the six vectors in $\mathbb{R}^{6}$ given by

The 3-polytope $Vx\leqslant \mathbf{1}$ is a bipyramid over a triangle (see Figure 8). The right half of the picture schematically shows the normal fan of the bipyramid (as a stereographic projection of the intersection of the normal fan with the sphere).

Figure 8

The bipyramid over a triangle and its normal fan.

By translating the faces of the bipyramid, we can split its four-valent vertices into pairs of three-valent vertices. For the spherical section of the normal fan, this means subdividing quadrilaterals by their diagonals. Let us apply the Gale diagram technique to study the arrangement of the type cones that correspond to different combinatorial types.

Let $V$ be the $6\times 3$ -matrix with rows $v_{i}$ . We have to find a $6\times 3$ -matrix $\bar{V}$ of rank three whose columns are orthogonal to those of $V$ . The matrix $\bar{V}$ is unique up to a multiplication from the right with an element of $\operatorname{GL}(\mathbb{R},3)$ . Since the vectors $v_{4},v_{5},v_{6}$ form a basis of $\mathbb{R}^{3}$ , the vectors $\bar{v}_{1},\bar{v}_{2},\bar{v}_{3}$ must do the same (see Lemma 1.26). Thus we may assume that

The remaining entries of $\bar{V}$ can be easily determined from the orthogonality condition between the columns of $V$ and $\bar{V}$

Recall that the map

projects the space of support vectors $h$ to its quotient by translations of the polytope $P(h)$ (see equation (2) and Definition 1.23). We identify $\mathbb{R}^{n-d}$ with a subspace of $\mathbb{R}^{n}$ via a right inverse $\unicode[STIX]{x1D704}$ of $\bar{V}^{\top }$ . In our case, we can put $\unicode[STIX]{x1D704}(e_{i})=e_{i}$ for $i=1,2,3$ so that $\mathbb{R}^{n-d}=\mathbb{R}^{3}$ is identified with the subspace $h_{4}=h_{5}=h_{6}=0$ of $\mathbb{R}^{6}$ . Geometrically, this corresponds to fixing the lower vertex of the bipyramid at the origin and varying only the heights $h_{1},h_{2},h_{3}$ .

The rows of $\bar{V}$ are the coordinates of six vectors forming the Gale diagram of $V$ . Since all of them lie in the subspace $h_{1}+h_{2}+h_{3}>0$ , we can conveniently draw the affine Gale diagram by intersecting the cones generated by $\bar{V}$ with the affine hyperplane $h_{1}+h_{2}+h_{3}=1$ (see Figure 9, left). (By a lucky coincidence, the vectors $\bar{v}_{i}$ lie in this plane.)

Figure 9

The Gale diagram of the face normals of a triangular bipyramid (left); the compatibility and the irredundancy domains (right).

Figure 9, right, shows the quotients $\operatorname{co}(V)$ and $\operatorname{ir}(V)$ of the compatibility domain and of the irredundancy domain. According to (9b), $\operatorname{co}(V)$ is the positive hull of $\bar{V}$ , which, in the affine Gale diagram, becomes the convex hull. According to (12b), $\operatorname{ir}(V)$ is the 2-core of $\bar{V}$ , which is shown as a shaded hexagon in Figure 9.

It is also possible to interpret Figure 9, right, in terms of positive and hyperbolic circuits (see equations (9c) and (12c)). The six positive circuits of the vector configuration $V$ are obtained from

by the action of the dihedral group. This particular circuit leads, according to (9b), to the inequality $h_{1}+2h_{2}\geqslant 0$ in the $h_{4}=h_{5}=h_{6}=0$ space, which determines the half-space containing vectors $\bar{v}_{3}$ and $\bar{v}_{5}$ in its boundary. The other five edges of the big hexagon shown in Figure 9 correspond to the other five positive circuits.

The lines bounding the irredundancy domain correspond to hyperbolic circuits (in this example, the inequalities in (12c) generated by the positive circuits turn out to be redundant). For example, the line highlighted in Figure 9 corresponds to the circuit

The principle “evaluations on $\bar{V}$ correspond to dependencies in $V$ ” (see (7)) and allow us to read off the signature of the circuit from the position of the line. Since the line separates $\bar{v}_{1}$ from $\bar{v}_{2}$ , $\bar{v}_{3}$ and $\bar{v}_{4}$ , the coefficient at $v_{1}$ has the sign opposite to those at $\bar{v}_{2}$ , $\bar{v}_{3}$ and $\bar{v}_{4}$ ; the points lying on the line correspond to zero coefficients.

In order to obtain the chamber fan of the vector configuration $\bar{V}$ , one has to draw the diagonals $\bar{v}_{1}\bar{v}_{4}$ , $\bar{v}_{2}\bar{v}_{5}$ and $\bar{v}_{3}\bar{v}_{6}$ in addition to those drawn already in Figure 9. The chambers in the interior of the 2-core are the type cones of $V$ . Figure 10 shows the subdivision of $\operatorname{clir}(V)$ into chambers and describes the faces of one of the full-dimensional type cones.

Figure 10

A type cone.

For any point $h\in \operatorname{clir}(V)$ (recall that we identified $\mathbb{R}^{3}$ with a subspace of $\mathbb{R}^{6}$ by putting $h_{4}=h_{5}=h_{6}$ ), the combinatorics of the corresponding polytope can be read off from the diagram. By Lemma 1.40, the normal fan of $P(h)$ contains the cone $\operatorname{pos}(V_{I})$ (equivalently, facets with normals $\{v_{i}\mid i\in I\}$ intersect along a face) if and only if $h$ lies in the relative interior of the positive hull of $\bar{V}_{[6]\setminus I}$ . For example, since the type cone highlighted in Figure 10 lies in $\operatorname{relint}\operatorname{pos}\{\bar{v}_{1},\bar{v}_{2},\bar{v}_{5}\}$ , the corresponding fan $\unicode[STIX]{x1D6E5}$ contains the cone spanned by $v_{3},v_{4},v_{6}$ . The normal fan corresponding to this type cone is shown in the center of Figure 11. This normal fan is simplicial, since the type cone is full-dimensional (compare Lemma 1.19).

The other fans in Figure 11 are associated with the faces of the depicted type cone. Note that the fans corresponding to boundary points of $\operatorname{clir}(V)$ are not using all of the vertices $v_{i}$ (compare Lemma 1.52).

Figure 11

The fans corresponding to the faces of a type cone.

Crossing from one fully dimensional type cone to an adjacent one corresponds to a “flip” (see Figure 12). The edge $F_{35}$ becomes replaced by the edge $F_{26}$ (compare the description of the faces of the type cones through vanishing edge lengths in Lemma 1.21). From a different point of view, boundaries between full-dimensional type cones correspond to (non-positive and non-hyperbolic) circuits of the vector configuration $V$ . A circuit of this form corresponds to contracting an edge of the polytope (see equation (4)). There are three such circuits

and they correspond to the hyperplanes

or, in our picture, to the lines

Figure 12

The flip $\{\{2,3,5\},\{3,5,6\}\}{\rightsquigarrow}\{\{2,3,6\},\{2,5,6\}\}$ .

The fan shown in Figure 13, left, is not polytopal. Indeed, since it contains $\operatorname{pos}\{v_{1},v_{6}\}$ , $\operatorname{pos}\{v_{2},v_{4}\}$ and $\operatorname{pos}\{v_{3},v_{5}\}$ , the corresponding point $\unicode[STIX]{x1D70B}(h)$ must lie in the intersection

which is empty. Similarly, the other two fans in Figure 13 are also non-polytopal. (One can also refer to Figure 11, where all, up to symmetry, polytopal fans with the 1-skeleton in $V$ are shown.)

Figure 13

Examples of non-polytopal fans.

2.1.1 Parallelepipeds with fixed face directions

The surface area of the parallelepiped $\{x\mid 0\leqslant \langle x,v_{i}\rangle \leqslant h_{i},i=1,2,3\}$ equals

where $D=|\text{det}(v_{1},v_{2},v_{3})|$ . This is a quadratic form of signature $(+,-,-)$ .

2.1.2 Polygons

The area of a polygon with support vector $h\in \widetilde{T}(\unicode[STIX]{x1D6FC})\subset \mathbb{R}^{n}$ equals

where the edge length $\ell _{i}(h)$ is a linear function of $h$ . Thus $\operatorname{area}(h)$ is a quadratic form. The associated symmetric bilinear form is

due to $(\unicode[STIX]{x2202}\operatorname{area}(h)/\unicode[STIX]{x2202}h_{i})=\ell _{i}(h)$ , which follows from a simple geometric argument.

The quadratic form $\operatorname{area}(h)$ has signature $(+,0,0,-,\ldots ,-)$ . This can be proved by induction on the number of edges of the polygon, as in [Reference Bavard and Ghys4], or using Minkowski’s inequality [Reference Schneider38, p. 321]. See also [Reference Izmestiev21, Lemma 2.14].

2.1.3 Polygonal prisms

Denote by $\operatorname{area}^{+}(h^{+})$ the surface area of a prism $(h,h_{n+1},h_{n+2})$ over the $n$ -gon. Here $v_{n+1}$ and $v_{n+2}$ are as in §1.3.3. Then

with the associated symmetric bilinear form

The restriction of $\operatorname{area}^{+}$ to $\mathbb{R}^{n}$ is $2\operatorname{area}$ , which, by the above results, has signature $(+,0,0,-,\ldots ,-)$ . The vector $(\mathbf{0},-1,1)$ belongs to the kernel of $\operatorname{area}^{+}$ (it corresponds to vertical translation). The vector $(\mathbf{1},-1,-1)$ is orthogonal to $\mathbb{R}^{n}\subset \mathbb{R}^{n+2}$ with respect to $\operatorname{area}^{+}$ and is negative. This implies that $\operatorname{area}^{+}$ has signature $(+,0,0,0,-,\ldots ,-)$ .

2.1.4 Triangular bipyramid

Let $v_{1},\ldots ,v_{6}\in \mathbb{R}^{3}$ be as in 1.3.4. The combinatorics of a polyhedron $P(h)$ with face normals $(v_{i})$ depend on $h$ . Let us compute $\operatorname{area}(\unicode[STIX]{x2202}P(h))$ for the type cone $\unicode[STIX]{x1D6E5}$ shaded in Figure 10.

The normal fan of $P(h)$ (the triangulation in the center of Figure 11) shows that $P(h)$ is a doubly truncated tetrahedron (see Figure 14). So

where

The surface area of a tetrahedron with fixed face normals is proportional to the squared length of any of its edges and the edge length is a linear function of the support vector. Thus

for some linear function $f_{1}$ . We have $f_{1}(h)=0$ if and only if the hyperplanes $H_{i}$ , $i\in \{2,3,4,5\}$ pass through a common point, that is, if and only if the system $\langle v_{i},x\rangle =h_{i}$ has a solution. Since $v_{2}+2v_{3}+2v_{4}+v_{5}=0$ , a solution exists if and only if $h_{2}+2h_{3}+2h_{4}+h_{5}=0$ . By restricting to $h_{4}=h_{5}=h_{6}=0$ as we have done in §1.3.4, we obtain

for some $c_{1}>0$ .

Figure 14

Representing $P(h)$ as a truncated tetrahedron.

Next, observe that

Each of the quantities $\operatorname{area}(F_{i}(\unicode[STIX]{x1D6F4}_{2}))$ is proportional to the square of a linear function $f_{2}(h)$ that vanishes when $\unicode[STIX]{x1D6F4}_{2}$ degenerates. Similarly to the previous paragraph, using (21), we find that $f_{2}(h)=h_{1}-2h_{2}-2h_{3}-3h_{4}$ , and hence

Here $c_{2}>0$ because the sum of areas of three faces of a tetrahedron is bigger than the area of its fourth face.

Finally, cutting off the tetrahedron $\unicode[STIX]{x1D6F4}_{3}$ yields

where

Since $f_{1}$ , $f_{2}$ and $f_{3}$ are linearly independent, $q_{\unicode[STIX]{x1D6E5}}(h)$ has signature $(+,-,-)$ .