A geometric approach for the upper bound theorem for Minkowski sums of convex polytopes

preprint2015arXivOpen access

Abstract

We derive tight expressions for the maximum number of kk-faces, 0≤k≤d−10\le{}k\le{}d-1, of the Minkowski sum, P1+...+PrP_1+...+P_r, of rr convex dd-polytopes P1,...,PrP_1,...,P_r in Rd\mathbb{R}^d, where d≥2d\ge{}2 and r<dr<d, as a (recursively defined) function on the number of vertices of the polytopes. Our results coincide with those recently proved by Adiprasito and Sanyal [2]. In contrast to Adiprasito and Sanyal's approach, which uses tools from Combinatorial Commutative Algebra, our approach is purely geometric and uses basic notions such as ff- and hh-vector calculus and shellings, and generalizes the methodology used in [15] and [14] for proving upper bounds on the ff-vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum P1+...+PrP_1+...+P_r as a section of the Cayley polytope C\mathcal{C} of the summands; bounding the kk-faces of P1+...+PrP_1+...+P_r reduces to bounding the subset of the (k+r−1)(k+r-1)-faces of C\mathcal{C} that contain vertices from each of the rr polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds.

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.