TY - JOUR

T1 - Reachability by paths of bounded curvature in a convex polygon

AU - Ahn, Heekap

AU - Cheong, Otfried

AU - Matoušek, Jiřǐ

AU - Vigneron, Antoine E.

N1 - KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: Work by Cheong was supported by Mid-career Researcher Program through NRF grant funded by the MEST (No. R01-2008-000-11607-0). Work by Ahn was supported by the National IT Industry Promotion Agency (NIPA) under the program of Software Engineering Technologies Development.

PY - 2012/1

Y1 - 2012/1

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/562037

UR - https://linkinghub.elsevier.com/retrieve/pii/S0925772111000617

UR - http://www.scopus.com/inward/record.url?scp=80053565782&partnerID=8YFLogxK

U2 - 10.1016/j.comgeo.2011.07.003

DO - 10.1016/j.comgeo.2011.07.003

M3 - Article

VL - 45

SP - 21

EP - 32

JO - Computational Geometry

JF - Computational Geometry

SN - 0925-7721

IS - 1-2

ER -