The maximum number of faces of the Minkowski sum of three convex polytopes

2012/11/26 by Karavelas, Menelaos I., Konaxis, Christos, Tzanaki, Eleni
#52B05 #52B11 #52C45 #68U05 #Combinatorics (math.CO) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1211.6089

Abstract

We derive tight expressions for the maximum number of k-faces, 0≤ k≤ d-1, of the Minkowski sum, P₁+P₂+P₃, of three d-dimensional convex polytopes P₁, P₂ and P₃, as a function of the number of vertices of the polytopes, for any d≥ 2. Expressing the Minkowski sum of the three polytopes as a section of their Cayley polytope C, the problem of counting the number of k-faces of P₁+P₂+P₃, reduces to counting the number of (k+2)-faces of the subset of C comprising of the faces that contain at least one vertex from each P_i. In two dimensions our expressions reduce to known results, while in three dimensions, the tightness of our bounds follows by exploiting known tight bounds for the number of faces of r d-polytopes, where r≥ d. For d≥ 4, the maximum values are attained when P₁, P₂ and P₃ are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves.

Related

• The maximum number of faces of the Minkowski sum of two convex polytopes
• A geometric approach for the upper bound theorem for Minkowski sums of\n convex polytopes
• Tight lower bounds on the number of faces of the Minkowski sum of convex polytopes via the Cayley trick
• Computing the Minkowski Sum of Convex Polytopes in \Re^d
• A linear equation for Minkowski sums of polytopes relatively in general position