# Motion planning of a ball amid segments in three dimensions

Published

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