We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
The Maximum Number of Faces of the Minkowski Sum of Two Convex Polytopes.
- Authors
Karavelas, Menelaos; Tzanaki, Eleni
- Abstract
We derive tight bounds for the maximum number of k-faces, $$0\le k\le d-1$$ , of the Minkowski sum, $$P_1+P_2$$ , of two d-dimensional convex polytopes $$P_1$$ and $$P_2$$ , as a function of the number of vertices of the polytopes. For even dimensions $$d\ge 2$$ , the maximum values are attained when $$P_1$$ and $$P_2$$ are cyclic d-polytopes with disjoint vertex sets. For odd dimensions $$d\ge 3$$ , the maximum values are attained when $$P_1$$ and $$P_2$$ are $$\lfloor \frac{d}{2}\rfloor $$ -neighborly d-polytopes, whose vertex sets are chosen appropriately from two distinct d-dimensional moment-like curves.
- Subjects
DISCRETE geometry; COMBINATORIAL geometry; MINKOWSKI geometry; CONVEX polytopes; EUCLIDEAN geometry
- Publication
Discrete & Computational Geometry, 2016, Vol 55, Issue 4, p748
- ISSN
0179-5376
- Publication type
Article
- DOI
10.1007/s00454-015-9726-6