Reachability by paths of bounded curvature in a convex polygon

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

doi:10.1016/j.comgeo.2011.07.003

Reachability by paths of bounded curvature in a convex polygon

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

Research output: Contribution to journal › Article › peer-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 language	English (US)
Pages (from-to)	21-32
Number of pages	12
Journal	Computational Geometry
Volume	45
Issue number	1-2
DOIs	https://doi.org/10.1016/j.comgeo.2011.07.003
State	Published - Jan 2012

ASJC Scopus subject areas

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

Access to Document

10.1016/j.comgeo.2011.07.003

Cite this

@article{536f7d9caf1a4a248ed1c1533ccfa7a9,

title = "Reachability by paths of bounded curvature in a convex polygon",

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. {\textcopyright} 2011 Elsevier B.V.",

author = "Heekap Ahn and Otfried Cheong and Ji{\v r}ǐ Matou{\v s}ek and Vigneron, {Antoine E.}",

note = "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.",

year = "2012",

month = jan,

doi = "10.1016/j.comgeo.2011.07.003",

language = "English (US)",

volume = "45",

pages = "21--32",

journal = "Computational Geometry",

issn = "0925-7721",

publisher = "Elsevier",

number = "1-2",

}

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

SN - 0925-7721

VL - 45

SP - 21

EP - 32

JO - Computational Geometry

JF - Computational Geometry

IS - 1-2

ER -

Reachability by paths of bounded curvature in a convex polygon

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this