On the Exact Maximum Complexity of Minkowski Sums of Polytopes
We present a tight bound on the exact maximum complexity of Minkowski sums of polytopes in R(3). In particular, we prove that the maximum number of facets of the Minkowski sum of k polytopes with m(1), m(2), ... , m(k) facets, respectively, is bounded from above by Sigma(1 <= i<j <= k) (2m(i) - 5)(2m(j) - 5) + Sigma(1 <= i <= k) m(i) + ((k)(2)). Given k positive integers m(1), m(2), ... , mk, we describe how to construct k polytopes with corresponding number of facets, such that the number of facets of their Minkowski sum is exactly Sigma 1 <= i<j <= k (2m(i) - 5)(2m(j) - 5) + Sigma(1 <= i <= k) m(i) + ((k)(2)). When k = 2, for example, the expression above reduces to 4m(1)m(2) - 9m(1) - 9m(2) + 26.
complexity minkowski sum polyhedra gaussian maps