Journal of Computational Geometry jocg.org THE MAXIMUM NUMBER OF FACES OF THE MINKOWSKI SUM OF THREE CONVEX POLYTOPES∗

Abstract. We derive tight expressions for the maximum number of k-faces, 0 ≤ k ≤ d−1, of the Minkowski sum, P1 +P2 +P3, of three d-dimensional convex polytopes P1, P2 and P3 in Rd, as a function of the number of vertices of the polytopes, for any d ≥ 2. Expressing the Minkowski sum as a section of the Cayley polytope C of its summands, counting the k-faces of P1 + P2 + P3 reduces to counting the (k + 2)-faces of C that contain vertices from each of the three polytopes. 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 in Rd, where r ≥ d. For d ≥ 4, the maximum values are attained when P1, P2 and P3 are d-polytopes, whose vertex sets are chosen appropriately from three distinct d-dimensional moment-like curves.