Secondary Polytopes

An ingenious construction of Gelfand, Kapranov, and Zelevinsky [1] associates to each triangulation of a set of n points x1,...,xn in Rd a point in Rn. The ith coordinate of this new point is the total volume of all simplices incident to xi in the triangulation. The convex hull of these new points is called the secondary polytope of the point configuration. It has dimension n-d-1, and its vertices correspond to the so-called regular triangulations of the point set.

The flip graph of a point configuration is the graph whose vertices are the triangulations of the configuration, and where two vertices are connected by an edge if there exists a bistellar operation transforming one triangulation into the other. The 1-skeleton of the secondary polytope is therefore the subgraph of the flip graph induced by the regular triangulations of the point configuration.

It is important to realize that the secondary polytope and the flip graph are NOT combinatorial invariants of a given point configuration, but depend on its metrical properties.

Reference

  1. I.M. Gelfand, M.M. Kapranov, and A.V. Zelevinsky: Discriminants, Resultants, and Multidimensional Determinants, Birkhäuser (1994).