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

Jean-Daniel Boissonnat 1 Sylvain Lazard 1
1 PRISME - Geometry, Algorithms and Robotics
CRISAM - Inria Sophia Antipolis - Méditerranée
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.
Type de document :
Communication dans un congrès
Symposium on Computational Geometry (SoCG'96), 1996, Philadelphia, United States. ACM, pp.242-251, 1996, 〈10.1145/237218.237393〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00442806
Contributeur : Sylvain Lazard <>
Soumis le : mardi 22 décembre 2009 - 16:11:23
Dernière modification le : jeudi 11 janvier 2018 - 16:22:53
Document(s) archivé(s) le : jeudi 17 juin 2010 - 22:08:42

Fichiers

ACM.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jean-Daniel Boissonnat, Sylvain Lazard. A polynomial-time algorithm for computing shortest paths of bounded curvature amidst moderate obstacles. Symposium on Computational Geometry (SoCG'96), 1996, Philadelphia, United States. ACM, pp.242-251, 1996, 〈10.1145/237218.237393〉. 〈inria-00442806〉

Partager

Métriques

Consultations de la notice

257

Téléchargements de fichiers

119