The Polytope of All Triangulations of a Point Configuration

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 \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.

1991 Mathematics Subject Classification: Primary 52B55; Secondary 90C27.

--> This manuscript contains graphics,
--> hence the dvi files might be incomplete.
Full text: dvi.gz 34 k, dvi 80 k, ps.gz 91 k, pdf 248k

Home Page of DOCUMENTA MATHEMATICA