MINKOWSKI ADDITION OF POLYTOPES - COMPUTATIONAL-COMPLEXITY AND APPLICATIONS TO GROBNER BASES

This paper deals with a problem from computational convexity and its application to computer algebra. This paper determines the complexity of computing the Minkowski sum of k convex polytopes in R(d), which are presented either in terms of vertices or in terms of facets. In particular, if the dimension d is fixed, the authors obtain a polynomial time algorithm for adding k polytopes with up to n vertices. The second part of this paper introduces dynamic versions of Buchberger's Grobner bases algorithm for polynomial ideals. Using the Minkowski addition of Newton polytopes, the authors show that the following problem can be solved in polynomial time for any finite set of polynomials T subset-of K[x1,...,x(d)], where d is fixed: Does there exist a term order tau such that T is a Grobner basis for its ideal with respect to tau? If not, find an optimal term order for T with respect to a natural Hilbert function criterion.