Jesús A. de Loera, Serkan Hosten, Francisco Santos, Bernd Sturmfels

摘要

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