Reachability by paths of bounded curvature in a convex polygon

Heekap Ahn, Otfried Cheong, Jiřǐ Matoušek, Antoine E. Vigneron

Research output: Contribution to journalArticlepeer-review

13 Scopus citations

Abstract

Let B be a point robot moving in the plane, whose path is constrained to forward motions with curvature at most 1, and let P be a convex polygon with n vertices. Given a starting configuration (a location and a direction of travel) for B inside P, we characterize the region of all points of P that can be reached by B, and show that it has complexity O(n). We give an O(n2) time algorithm to compute this region. We show that a point is reachable only if it can be reached by a path of type CCSCS, where C denotes a unit circle arc and S denotes a line segment. © 2011 Elsevier B.V.
Original languageEnglish (US)
Pages (from-to)21-32
Number of pages12
JournalComputational Geometry
Volume45
Issue number1-2
DOIs
StatePublished - Jan 2012

ASJC Scopus subject areas

  • Control and Optimization
  • Computational Theory and Mathematics
  • Computational Mathematics
  • Geometry and Topology
  • Computer Science Applications

Fingerprint

Dive into the research topics of 'Reachability by paths of bounded curvature in a convex polygon'. Together they form a unique fingerprint.

Cite this