Math @ Duke

Publications [#235406] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Biedl, T; Lazard, S; Robbins, S; Suri, S; Whitesides, S, Curvatureconstrained shortest paths in a convex polygon,
in Fourteenth Annual Symposium on Computational Geometry,
Proceedings of the Annual Symposium on Computational Geometry
(1998),
pp. 392401
(last updated on 2018/12/16)
Abstract: Let B be a point robot moving in the plane, whose path is constrained to have curvature at most 1, and let P be a convex polygon with n vertices. We study the collisionfree, optimal pathplanning problem for B moving between two configurations inside P (a configuration specifies both a location and a direction of travel). We present an O(n2 log n) time algorithm for determining whether a collisionfree path exists for B between two given configurations. If such a path exists, the algorithm returns a shortest one. We provide a detailed classification of curvatureconstrained shortest paths inside a convex polygon and prove several properties of them, which are interesting in their own right. Some of the properties are quite general and shed some light on curvatureconstrained shortest paths amid obstacles.


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

