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
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$.
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
Cité par Sources :