Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke



Publications [#235418] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Sharir, M, Motion planning of a ball amid segments in three dimensions, in Tenth Annual ACM-SIAM Symposium on Discrete Algorithms, Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (1999), pp. 21-30
    (last updated on 2018/10/22)

    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.
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320