Motion planning of a ball amid segments in three dimensions
Let S be a set of n pairwise disjoint segments in R3, and let B be a ball of radius 1. The free configuration space F of B amid S is the set of all placements of B at which (the interior of) B does not intersect any segment of S. We show that the combinatorial complexity of F is O(n5/2+ε), for any ε>0, with the constant of proportionality depending on ε. This is the first subcubic bound on the complexity of the free configuration space even when S is a set of lines in R3. We also present a randomized algorithm that can compute the boundary o the free configuration space in O(n5/2+ε) expected time.