Constructions and complexity of secondary polytopes (Q750909)

The paper presents a self-contained and comprehensive study of secondary polytopes. The secondary polytope \(\Sigma\) (\({\mathcal A})\) of a configuration \({\mathcal A}\) of n points in affine (d-1)-space is an (n-d)- polytope whose vertices correspond to regular triangulations of conv(\({\mathcal A}).\) Besides the original Gelfand-Kapranov-Zelevinsky construction a construction of \(\Sigma\) (\({\mathcal A})\) as the projection of a universal polytope \({\mathcal U}({\mathcal A})\) is given. Especially interesting is a third construction of \(\Sigma\) (\({\mathcal A})\) using Gale transforms. This point of view is the most constructive one. It leads to an algorithm for computing all regular triangulations of \({\mathcal A}\). The rest of the paper deals with other aspects of the computational complexity of secondary polytopes (for instance a bound for the number of faces of \(\Sigma\) (A) is given).