  Approximation problems involving a single convex body in $d$-dimensional
space have received a great deal of attention in the computational geometry
community. In contrast, works involving multiple convex bodies are generally
limited to dimensions $d \leq 3$ and/or do not consider approximation. In this
paper, we consider approximations to two natural problems involving multiple
convex bodies: detecting whether two polytopes intersect and computing their
Minkowski sum. Given an approximation parameter $\varepsilon > 0$, we show how
to independently preprocess two polytopes $A,B$ into data structures of size
$O(1/\varepsilon^{(d-1)/2})$ such that we can answer in polylogarithmic time
whether $A$ and $B$ intersect approximately. More generally, we can answer this
for the images of $A$ and $B$ under affine transformations. Next, we show how
to $\varepsilon$-approximate the Minkowski sum of two given polytopes defined
as the intersection of $n$ halfspaces in $O(n \log(1/\varepsilon) +
1/\varepsilon^{(d-1)/2 + \alpha})$ time, for any constant $\alpha > 0$.
Finally, we present a surprising impact of these results to a well studied
problem that considers a single convex body. We show how to
$\varepsilon$-approximate the width of a set of $n$ points in $O(n
\log(1/\varepsilon) + 1/\varepsilon^{(d-1)/2 + \alpha})$ time, for any constant
$\alpha > 0$, a major improvement over the previous bound of roughly $O(n +
1/\varepsilon^{d-1})$ time.
