Pipes, cigars, and kreplach: the union of Minkowski sums in three dimensions

Let Omega be a set of pairwise-disjoint polyhedral obstacles in R-3 With a total of n vertices, and let B be a ball in R-3. We show that the combinato rial complexity of the free configuration space F of B amid Omega, i.e., (t he closure of) the set of all placements of B at which B does not intersect any obstacle, is O (n(2+epsilon)), for any epsilon > 0; the constant of pr oportionality depends on epsilon. This upper bound almost matches the known quadratic lower bound on the maximum possible complexity of F. The special case in which Omega is a set of lines is studied separately. We also prese nt a few extensions of this result, including a randomized algorithm for co mputing the boundary of F whose expected running time is O (n(2+epsilon)), for any epsilon > 0.