The figure on the left shows the Minkowski sum of three tetrahedra rotated
about the $Y$ axis
$0$,
$60$120^{} respectively,
and the Gaussian map of the Minkowski sum. The tetrahedra are constructed to
maxmize the number of facets in the Minkowski sum, which is the number of
vertices in its dual Gaussian map. You can view the individual summands and
their Minkowski sums, the primal shapes and the dual Gaussian maps, using the
player interactive program.
We present a tight bound on the exact maximum complexity of Minkowski
sums of convex polyhedra in
$$^{3}.
In particular, we prove that the maximum number of facets of the Minkowski
sum of two convex polyhedra with $m$ and $n$ facets
respectively is bounded from above by $f(m,n)\; =\; 4mn\; -\; 9m\; -\; 9n\; +\; 26$.
Given two positive integers $m$ and $n$, we describe how
to construct two convex polyhedra with $m$ and $n$ facets
respectively, such that the number of facets of their Minkowski sum is
exactly $f(m,n)$. We generalize the construction to yield a lower
bound on the maximum complexity of Minkowski sums of many convex polyhedra
in ^{3}.
That is, given $k$ positive integers $m\_1,m\_2,...,m\_k$,
we describe how to construct $k$ convex polyhedra with corresponding
number of facets, such that the number of facets of their Minkowski sum is
exactly
$\sum $_{1 i < j k}(2m_{i} - 5)(2m_{j} - 5) + binom(k,2).
We also provide a conservative upper bound for the general case. |