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 combinatorial complexity of the free configuration space F of B amid\Omega\Gamma i.e., (the closure of) the set of all placements of B at which B does not intersect any obstacle, is O(n 2+" ), for any " ? 0; the constant of proportionality depends on ". 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, for which F is a the complement of the union of n congruent cylinders, is studied separately. We also present several extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n 2+" ), for any " ? 0. 0 A preliminary version of this paper appeared in Proc. 15th Annual ACM Symposium on Computational Geometry, 1999, pp. 143--153. Work by P.A. was supported by Army R..