iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/BFB0049413
Convex tours of bounded curvature | SpringerLink
Skip to main content
Springer Nature Link
Log in

Convex tours of bounded curvature

  • Conference paper
  • First Online:
Algorithms — ESA '94 (ESA 1994)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 855))

Included in the following conference series:

  • 151 Accesses

Abstract

We consider the motion planning problem for a point constrained to move along a smooth closed convex path of bounded curvature. The workspace of the moving point is bounded by a convex polygon with m vertices, containing an obstacle in a form of a simple polygon with n vertices. We present an O(m+n) time algorithm finding the path, going around the obstacle, whose curvature is the smallest possible.

This work has been supported in part by the ESPRIT Basic Research Actions Nr. 7141 (ALCOM II) and Nr. 6546 (PROMotion), NSERC, FCAR and FODAR.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

References

  1. A. Aggarwal, L. J. Guibas, J. Saxe, and P. W. Shor. A linear-time algorithm for computing the Voronoi diagram of a convex polygon. Discrete Comput. Geom., 4:591–604, 1989.

    Article  MathSciNet  Google Scholar 

  2. J. Canny, B. R. Donald, J. Reif, and P. Xavier. On the complexity of kinodynamic planning. In Proc. 29th Annu. IEEE Sympos. Found. Comput. Sci., pages 306–316, 1988.

    Google Scholar 

  3. L. E. Dubins. On curves of minimal length with a constraint on average curvature and with prescribed initial and terminal positions and tangents. Amer. J. Math., 79:497–516, 1957.

    MATH  MathSciNet  Google Scholar 

  4. S. Fortune and G. Wilfong. Planning constrained motion. In Proc. 20th Annu. ACM Sympos. Theory Comput., pages 445–459, 1988.

    Google Scholar 

  5. P. Jacobs and J. Canny. Planning smooth paths for mobile robots. In Proc. IEEE Internat. Conf. Robot. Autom., pages 2–7, 1989.

    Google Scholar 

  6. D. G. Kirkpatrick. Optimal search in planar subdivisions. SIAM J. Comput., 12:28–35, 1983.

    MATH  MathSciNet  Google Scholar 

  7. J.-C. Latombe. Robot Motion Planning. Kluwer Academic Publishers, Boston, 1991.

    Google Scholar 

  8. C. Ó'Dúnlaing. Motion-planning with inertial constraints. Algorithmica, 2:431–475, 1987.

    MATH  MathSciNet  Google Scholar 

  9. M. H. Overmars. A random approach to motion planning. Report RUU-CS-92-32, Dept. Comput. Sci., Univ. Utrecht, Utrecht, Netherlands, 1992.

    Google Scholar 

  10. F. P. Preparata. The medial axis of a simple polygon. In Proc. 6th Internat. Sympos. Math. Found. Comput. Sci., volume 53 of Lecture Notes in Computer Science, pages 443–450. Springer-Verlag, 1977.

    Google Scholar 

  11. J. H. Reif and M. Sharir. Motion planning in the presence of moving obstacles. In Proc. 26th Annu. IEEE Sympos. Found. Comput. Sci., pages 144–154, 1985.

    Google Scholar 

  12. J. T. Schwartz and M. Sharir. Algorithmic motion planning in robotics. In J. van Leeuwen, editor, Algorithms and Complexity, volume A of Handbook of Theoretical Computer Science, pages 391–430. Elsevier, Amsterdam, 1990.

    Google Scholar 

  13. P. Švestka. A probabilistic approach to motion planning for car-like robots. Report RUU-CS-93-18, Dept. Comput. Sci., Univ. Utrecht, Utrecht, Netherlands, 1993.

    Google Scholar 

  14. G. Wilfong. Motion planning for an autonomous vehicle. In Proc. IEEE Internat. Conf. Robot. Autom., pages 529–533, 1988.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INRIA, 2004 Route des Lucioles, B.P.109, 06561, Valbonne cedex, France

    Jean-Daniel Boissonnat & Olivier Devillers

  2. Dép. d'informatique, Université du Québec à Hull, Canada

    Jurek Czyzowicz

  3. Dép. d'informatique et de mathématique, Université du Québec à Chicoutimi, Canada

    Jean-Marc Robert

  4. URA 1376, Lab. I3S, INRIA and CNRS, 250 rue Albert Einstein, 06560, Sophia Antipolis, Valbonne, France

    Mariette Yvinec

Authors
  1. Jean-Daniel Boissonnat
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Jurek Czyzowicz
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Olivier Devillers
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Jean-Marc Robert
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Mariette Yvinec
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Jan van Leeuwen

Rights and permissions

Reprints and permissions

Copyright information

© 1994 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Boissonnat, JD., Czyzowicz, J., Devillers, O., Robert, JM., Yvinec, M. (1994). Convex tours of bounded curvature. In: van Leeuwen, J. (eds) Algorithms — ESA '94. ESA 1994. Lecture Notes in Computer Science, vol 855. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0049413

Download citation

  • DOI: https://doi.org/10.1007/BFb0049413

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-58434-6

  • Online ISBN: 978-3-540-48794-4

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation