Motion planning of a ball amid segments in three dimensions


Journal Article

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.

Duke Authors

Cited Authors

  • Agarwal, PK; Sharir, M

Published Date

  • January 1, 1999

Published In

  • Proceedings of the Annual Acm Siam Symposium on Discrete Algorithms

Start / End Page

  • 21 - 30

Citation Source

  • Scopus