Math @ Duke

Publications [#235421] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Aronov, B; Sharir, M, Motion planning for a convex polygon in a polygonal environment,
Discrete & Computational Geometry, vol. 22 no. 2
(1999),
pp. 201221, ISSN 01795376
(last updated on 2018/05/26)
Abstract: We study the motionplanning problem for a convex mgon P in a planar polygonal environment Q bounded by n edges. We give the first algorithm that constructs the entire free configuration space (the threedimensional space of all free placements of P in Q) in time that is nearquadratic in mn, which is nearly optimal in the worst case. The algorithm is also conceptually simple. Previous solutions were incomplete, more expensive, or produced only part of the free configuration space. Combining our solution with parametric searching, we obtain an algorithm that finds the largest placement of P in Q in time that is also nearquadratic in mn. In addition, we describe an algorithm that preprocesses the computed free configuration space so that reachability queries can be answered in polylogarithmic time.


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

