Maximal f-vectors of Minkowski sums of large numbers of polytopes

preprint2010arXivOpen access

Abstract

It is known that in the Minkowski sum of rr polytopes in dimension dd, with r<dr<d, the number of vertices of the sum can potentially be as high as the product of the number of vertices in each summand. However, the number of vertices for sums of more polytopes was unknown so far. In this paper, we study sums of polytopes in general orientations, and show a linear relation between the number of faces of a sum of rr polytopes in dimension dd, with r≥dr\geq d, and the number of faces in the sums of less than dd of the summand polytopes. We deduce from this exact formula a tight bound on the maximum possible number of vertices of the Minkowski sum of any number of polytopes in any dimension. In particular, the linear relation implies that a sum of rr polytopes in dimension dd has a number of vertices in O(nd−1)O(n^{d-1}) of the total number of vertices in the summands, even when r≥dr\geq d. This bound is tight, in the sense that some sums do have that many vertices.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.