Math @ Duke

Publications [#235418] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Sharir, M, Motion planning of a ball amid segments in three dimensions,
in Tenth Annual ACMSIAM Symposium on Discrete Algorithms,
Proceedings of the Annual ACMSIAM Symposium on Discrete Algorithms
(1999),
pp. 2130
(last updated on 2018/03/21)
Abstract: 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.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

