The polytope of all triangulations of a point configuration

Abstract

We study the convex hull $P_{\mathcal{A}}$ of the 0-1 incidence vectors of all triangulations of a point configuration $\mathcal{A}$. This was called the universal polytope in citeBIFIST. The affine span of $P_{\mathcal{A}}$ is described in terms of the co-circuits of the oriented matroid of $\mathcal{A}$. Its intersection with the positive orthant is a quasi-integral polytope $Q_{\mathcal{A}}$ whose integral hull equals $P_{\mathcal{A}}$. We present the smallest example where $Q_{\mathcal{A}}$ and $P_{\mathcal{A}}$ differ. The duality theory for regular triangulations in citeBIGEST is extended to cover all triangulations. We discuss potential applications to enumeration and optimization problems regarding all triangulations.