The polytope of all triangulations of a point configuration
Open Access
- 1 January 1996
- journal article
- Published by European Mathematical Society - EMS - Publishing House GmbH in Documenta Mathematica
- Vol. 1, 103-119
Abstract
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.Keywords
This publication has 3 references indexed in Scilit:
- Triangulations of cyclic polytopes and higher Bruhat ordersMathematika, 1997
- Projections of polytopes and the generalized baues conjectureDiscrete & Computational Geometry, 1996
- On the Set-Covering Problem: II. An Algorithm for Set PartitioningOperations Research, 1975