Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-16T20:08:54.783Z Has data issue: false hasContentIssue false

Diameter, Decomposability, and Minkowski Sums of Polytopes

Published online by Cambridge University Press:  17 December 2018

Antoine Deza
Affiliation:
Advanced Optimization Laboratory, McMaster University, Hamilton, Ontario, Canada Email: deza@mcmaster.ca
Lionel Pournin
Affiliation:
LIPN, Université Paris 13, Villetaneuse, France Email: lionel.pournin@univ-paris13.fr
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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$.

Information

Type
Article
Copyright
© Canadian Mathematical Society 2018