Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases

Source abstract

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 $\mathbb{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 Gröbner 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 $\mathcal{T} \subset K [ x_1 , \ldots ,x_d ]$, where d is fixed: Does there exist a term order $\tau$ such that $\mathcal{T}$ is a Gröbner basis for its ideal with respect to $\tau$? If not, find an optimal term order for $\mathcal{T}$ with respect to a natural Hilbert function criterion.