HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

A polynomial-time algorithm for computing shortest paths of bounded curvature amidst moderate obstacles

Jean-Daniel Boissonnat 1 Sylvain Lazard 2
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
2 ISA - Models, algorithms and geometry for computer graphics and vision
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : In this paper, we consider the problem of computing shortest paths of bounded curvature amidst obstacles in the plane. More precisely, given two prescribed initial and final configurations (specifying the location and the direction of travel) and a set of obstacles in the plane, we want to compute a shortest $C^1$ path joining those two configurations, avoiding the obstacles, and with the further constraint that, on each $C^2$ piece, the radius of curvature is at least 1. In this paper, we consider the case of moderate obstacles (as introduced by Agarwal et al.) and present a polynomial-time exact algorithm to solve this problem.
Document type :
Journal articles
Complete list of metadata

https://hal.inria.fr/inria-00099509
Contributor : Sylvain Lazard Connect in order to contact the contributor
Submitted on : Tuesday, December 15, 2009 - 3:01:39 PM
Last modification on : Friday, February 4, 2022 - 3:16:48 AM
Long-term archiving on: : Monday, April 5, 2010 - 11:52:14 PM

File

REVISED_version.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Jean-Daniel Boissonnat, Sylvain Lazard. A polynomial-time algorithm for computing shortest paths of bounded curvature amidst moderate obstacles. International Journal of Computational Geometry and Applications, World Scientific Publishing, 2003, 13 (3), pp.189-229. ⟨10.1142/S0218195903001128⟩. ⟨inria-00099509⟩

Share

Metrics

Record views

61

Files downloads

141