The polytope of all triangulations of a point configuration
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.
point configuration in d-dim. Euclidean space
scientific article; zbMATH DE number 897859