2026-07-20T05:05:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:5142 2024-03-06T10:35:50Z ddc:004 open_access

A Geometric Approach for the Upper Bound Theorem for Minkowski Sums of Convex Polytopes Karavelas, Menelaos I. Tzanaki, Eleni Convex polytopes Minkowski sum upper bound We derive tight expressions for the maximum number of k-faces, k=0,...,d-1, of the Minkowski sum, P_1+...+P_r, of r convex d-polytopes P_1,...,P_r in R^d, where d >= 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 [1]. 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 [10] and [9] 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+...+P_r as a section of the Cayley polytope C of the summands; bounding the k-faces of P_1+...+P_r reduces to bounding the subset of the (k+r-1)-faces of C that contain vertices from each of the r polytopes. We end our paper with a sketch of an explicit construction that establishes the tightness of the upper bounds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Menelaos I. Karavelas and Eleni Tzanaki 2015 Is Part Of LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SOCG.2015.81 urn:nbn:de:0030-drops-51428 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.81 eng https://creativecommons.org/licenses/by/3.0/legalcode