Abstract
It is known that in the Minkowski sum of r polytopes in dimension d, with r<d, the number of vertices of the sum can be as high as the product of the number of vertices in each summand. However, the number of vertices for sums of more polytopes was unknown so far.
In this paper, we study sums of polytopes and prove a linear relation between the number of faces of a sum of r polytopes in dimension d, with r≥d, and the number of faces in the sums of less than d of the summand polytopes. We deduce from this result a bound on the maximum possible number of vertices of the Minkowski sum of any number of polytopes in any dimension. In particular, the linear relation implies that a sum of r polytopes in dimension d, where summands have n vertices in total, has less than \({n \choose{d-1}}\) vertices, even when r≥d.
Finally, we present a construction for any given number of vertices in summands and show that no other sum can achieve more vertices, establishing a precise tight bound.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Fogel, E., Halperin, D., Weibel, C.: On the exact maximum complexity of Minkowski sums of polytopes. Discrete Comput. Geom. 42(4), 654–669 (2009)
Fukuda, K., Weibel, C.: On f-vectors of Minkowski additions of convex polytopes. Discrete Comput. Geom. 37, 503–516 (2007)
Fukuda, K., Weibel, C.: A linear equation for Minkowski sums of polytopes relatively in general position. Eur. J. Comb. 31(2), 565–573 (2010). Combinatorics and geometry
Gritzmann, P., Sturmfels, B.: Minkowski addition of polytopes: computational complexity and applications to Gröbner bases. SIAM J. Discrete Math. 6(2), 246–269 (1993)
Halperin, D., Kavraki, L.E., Latombe, J.-C.: Robotics. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, Chap. 48, pp. 1065–1093. CRC Press, Boca Raton (2004)
Karavelas, M., Tzanaki, E.: The maximum number of faces of the Minkowski sum of two convex polytopes. In: ACM-SIAM Symposium on Discrete Algorithms (2012)
Koltun, V., Sharir, M.: On overlays and minimization diagrams. Discrete Comput. Geom. 41(3), 385–397 (2009)
Lozano-Pérez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. Commun. ACM 22(10), 560–570 (1979)
Pachter, L., Sturmfels, B. (eds.): Algebraic Statistics for Computational Biology. Cambridge University Press, New York (2005)
Sanyal, R.: Topological obstructions for vertex numbers of Minkowski sums. J. Comb. Theory, Ser. A 116(1), 168–179 (2009)
Weibel, C.: Minkowski sums of polytopes: combinatorics and computation. PhD thesis, EPFL, Lausanne (2007)
Zhang, H.: Partially observable Markov decision processes: a geometric technique and analysis. Oper. Res., doi:10.1287/opre.1090.0697 (2009)
Ziegler, G.M.: Lectures on Polytopes. Graduate Texts in Mathematics, vol. 152. Springer, New York (1995)
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Weibel, C. Maximal f-Vectors of Minkowski Sums of Large Numbers of Polytopes. Discrete Comput Geom 47, 519–537 (2012). https://doi.org/10.1007/s00454-011-9385-1
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00454-011-9385-1