The polytope of all triangulations of a point configuration
Serkan Hoşten, Jesús A. De Loera, Francisco Santos, Bernd Sturmfels · Documenta Mathematica · 1996
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 called the universal polytope in citeBIFIST. 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 citeBIGEST is extended to cover all triangulations. We discuss potential applications to enumeration and optimization problems regarding all triangulations.