Motion planning of a ball amid segments in three dimensions
Pankaj K. Agarwal, Micha Sharir · 1999
Let S be a set of n pairwise disjoint segments in R 3 , 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(n 5=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 R 3 . We also present a randomized algorithm that can compute the boundary of the free configuration space in O(n 5=2+" ) expected time. 1 Introduction Problem statement. Let S be a collection of n pairwise disjoint segments in R 3 , and let B be a ball of radius 1. We regard S as a set of obstacles and consider the motion-planning problem in which B is allowed to move (translate) freely in R 3 without intersecting any segment of S. The free configuration space F of B with respect to S is the set of ...