The polytope of all triangulations of a point configuration (Q1917625): Difference between revisions

Let \(A = \{a_1, \ldots, a_n\}\) be a point configuration in \(\mathbb R^d\). The set of regular triangulations of \(A\) is well-understood by its bijection with the vertices of the so-called secondary polytope. Here the authors are mainly concerned with the set of non-regular triangulations of \(A\). More precisely, they investigate the convex hull \(P_A\) of the 0-1 incidence vectors of all triangulations of \(A\), being isomorphic to the so-called universal polytope which was introduced by \textit{L. J. Billera, P. Filliman} and \textit{B. Sturmfels} in [Adv. Math. 83, No. 2, 155--179 (1990; Zbl 0714.52004)]. E.g., the affine span of \(P_A\) is described in terms of the cocircuits of the oriented matroid of \(A\). Its intersection with the positive orthant is a quasi-integral polytope \(Q_A\) whose integral hull equals \(P_A\). The smallest example, where \(P_A\) and \(Q_A\) differ, is described, too. Furthermore, the known duality theory for regular triangulations is extended to all triangulations. Finally, some applications are discussed, e.g. to optimization problems referring to the set of all triangulations.