Geodesic
Diameter, Decomposability, and Minkowski Sums of Polytopes
Canadian mathematical bulletin, Tome 62 (2019) no. 4, pp. 741-755

Voir la notice de l'article provenant de la source Cambridge University Press

We investigate how the Minkowski sum of two polytopes affects their graph and, in particular, their diameter. We show that the diameter of the Minkowski sum is bounded below by the diameter of each summand and above by, roughly, the product between the diameter of one summand and the number of vertices of the other. We also prove that both bounds are sharp. In addition, we obtain a result on polytope decomposability. More precisely, given two polytopes $P$ and $Q$, we show that $P$ can be written as a Minkowski sum with a summand homothetic to $Q$ if and only if $P$ has the same number of vertices as its Minkowski sum with $Q$.
DOI : 10.4153/S0008439518000668
Mots-clés : Minkowski sum, polytope, diameter, decomposability 
Deza, Antoine; Pournin, Lionel. Diameter, Decomposability, and Minkowski Sums of Polytopes. Canadian mathematical bulletin, Tome 62 (2019) no. 4, pp. 741-755. doi: 10.4153/S0008439518000668
@article{10_4153_S0008439518000668,
     author = {Deza, Antoine and Pournin, Lionel},
     title = {Diameter, {Decomposability,} and {Minkowski} {Sums} of {Polytopes}},
     journal = {Canadian mathematical bulletin},
     pages = {741--755},
     year = {2019},
     volume = {62},
     number = {4},
     doi = {10.4153/S0008439518000668},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/S0008439518000668/}
}
TY  - JOUR
AU  - Deza, Antoine
AU  - Pournin, Lionel
TI  - Diameter, Decomposability, and Minkowski Sums of Polytopes
JO  - Canadian mathematical bulletin
PY  - 2019
SP  - 741
EP  - 755
VL  - 62
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.4153/S0008439518000668/
DO  - 10.4153/S0008439518000668
ID  - 10_4153_S0008439518000668
ER  - 
%0 Journal Article
%A Deza, Antoine
%A Pournin, Lionel
%T Diameter, Decomposability, and Minkowski Sums of Polytopes
%J Canadian mathematical bulletin
%D 2019
%P 741-755
%V 62
%N 4
%U http://geodesic.mathdoc.fr/articles/10.4153/S0008439518000668/
%R 10.4153/S0008439518000668
%F 10_4153_S0008439518000668

[1] Adiprasito, K. A. and Sanyal, R., Relative Stanley–Reisner theory and upper bound theorems for Minkowski sums . Publ. Math. Inst. Hautes Études Sci. 124(2016), 99–163. Google Scholar | DOI

[2] Deza, A., Deza, A., Guan, Z., and Pournin, L., Distance between vertices of lattice polytopes. Optimization letters, to appear. Google Scholar

[3] Deza, A., Manoussakis, G., and Onn, S., Primitive zonotopes . Discrete Comput. Geom. 60(2018), 27–39. Google Scholar | DOI

[4] Fukuda, K., Lecture notes: Polyhedral computation . ETH Zurich, Switzerland, http://www-oldurls.inf.ethz.ch/personal/fukudak/lect/pclect/notes2015/. Google Scholar

[5] Fukuda, K. and Weibel, C., f-Vectors of Minkowski additions of convex polytopes . Discrete Comput. Geom. 37(2007), 503–516. Google Scholar | DOI

[6] Grünbaum, B., Convex polytopes . Graduate Texts in Mathematics, 221, Springer, 2003. Google Scholar | DOI

[7] Kallay, M., Decomposability of polytopes . Israel J. Math. 41(1982), 235–243. Google Scholar | DOI

[8] Meyer, W., Indecomposable polytopes . Trans. Amer. Math. Soc. 190(1974), 77–86. Google Scholar | DOI

[9] Przesławski, K. and Yost, D., Decomposability of polytopes . Discrete Comput. Geom. 39(2008), 460–468. Google Scholar | DOI

[10] Santos, F., A counterexample to the Hirsch conjecture . Ann. of Math. 176(2012), 383–412. Google Scholar | DOI

[11] Shephard, G. C., Decomposable convex polyhedra . Mathematika 10(1963), 89–95. Google Scholar | DOI

[12] Ziegler, G. M., Lectures on polytopes . Graduate Texts in Mathematics, 152, Springer, 1995. Google Scholar | DOI

Cité par Sources :