Reachability by Paths of Bounded Curvature in a Convex Polygon

2010/08/25 by Ahn, Hee-Kap, Cheong, Otfried, Matoušek, Jirí +1
#Computational Geometry (cs.CG) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1008.4244

Abstract

Let B be a point robot moving in the plane, whose path is constrained to forward motions with curvature at most one, 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(n²) 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.

Related

• Convex Tours of Bounded Curvature
• On the Reachability of 3-Dimensional Paths with a Prescribed Curvature Bound
• The Cost of Bounded Curvature
• Fixed-Time State Transfer via Pontryagin Extremals
• Shortest Paths of Mutually Visible Robots