Pipes, Cigars, and Kreplach: the Union of Minkowski Sums in Three Dimensions

Let Ω be a set of pairwise-disjoint polyhedral obstacles in R ³ with a total of n vertices, and let B be a ball in R ³. We show that the combinatorial complexity of the free configuration space F of B amid Ω:, 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 Ω is a set of lines is studied separately. We also present a few extensions of this result, including a randomized algorithm for computing the boundary of F whose expected running time is O(n ^2+ε ). Received July 6, 1999, and in revised form April 25, 2000. Online publication August 18, 2000.