We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes.
- Authors
Karavelas, Menelaos; Tzanaki, Eleni
- Abstract
We derive tight expressions for the maximum number of k-faces, $$0\le {}k\le {}d-1$$ , of the Minkowski sum, $$P_1+\cdots +P_r$$ , of r convex d-polytopes $$P_1,\ldots ,P_r$$ in $${\mathbb {R}}^d$$ , where $$d\ge {}2$$ and $$r<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 (Publ Math Inst Hautes Etudes Sci. doi:, 2016). 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 $$f$$ - and h-vector calculus, stellar-subdivisions and shellings, and generalizes the methodology used in Karavelas and Tzanaki (Discrete Comput Geom 55:748-785, 2016) and Karavelas et al. (J Comput Geom 6(1):21-74, 2015) for proving upper bounds on the $$f$$ -vector of the Minkowski sum of two and three convex polytopes, respectively. The key idea behind our approach is to express the Minkowski sum $$P_1+\cdots +P_r$$ as a section of the Cayley polytope $${\mathcal {C}}$$ of the summands; bounding the k-faces of $$P_1+\cdots +P_r$$ reduces to bounding the subset of the $$(k+r-1)$$ -faces of $${\mathcal {C}}$$ that contain vertices from each of the r polytopes. We end our paper with an explicit construction that establishes the tightness of the upper bounds.
- Subjects
GEOMETRIC approach; MINKOWSKI geometry; CONVEX polytopes; COMMUTATIVE algebra; DISCRETE geometry; COMBINATORIAL geometry
- Publication
Discrete & Computational Geometry, 2016, Vol 56, Issue 4, p966
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-016-9818-y