Publications

### Server    domino.mpi-inf.mpg.de

 Proceedings Article, Paper @InProceedings Beitrag in Tagungsband, Workshop
 Author, Editor
 Editor(s): Paterson, Mike dblp
 BibTeX cite key*: Leejhc2000
 Title, Booktitle
 Title*: Approximation of Curvature-constrained Shortest Paths through a Sequence of Points Booktitle*: Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
 Event, URLs
 Conference URL:: http://www.mpi-sb.mpg.de/~conf2000/esa2000/ Downloading URL: Event Address*: Saarbrücken,Germany Language: English Event Date* (no longer used): September,5 - September,8 Organization: Event Start Date: 22 January 2022 Event End Date: 22 January 2022
 Publisher
 Name*: Springer URL: Address*: Berlin, Germany Type: Extended Abstract
 Vol, No, Year, pp.
 Series: Lecture Notes in Computer Science
 Volume: 1879 Number: Month: September Pages: 314-325 Year*: 2000 VG Wort Pages: ISBN/ISSN: Sequence Number: DOI:
 (LaTeX) 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 $\X$ denote a sequence of $n$ points. Let $s$ be the length of the shortest curvature-constrained path for $B$ that visits the points of $\X$ in the given order. We show that if the points of $\X$ are given \emph{on-line} and the robot has to respond to each point immediately, there is no strategy that guarantees a path whose length is at most~$f(n)s$, for any finite function~$f(n)$. On the other hand, if all points are given at once, a path with length at most $5.03 s$ can be computed in linear time. In the \emph{semi-online} case, where the robot not only knows the next input point but is able to see'' the future input points included in the disk with radius $R$ around the robot, a path of length $(5.03 + O(1/R))s$ can be computed. Keywords: Computational Geometry, Curvature constraint, Path planning Download Access Level:

 Correlation
 MPG Unit: Max-Planck-Institut für Informatik MPG Subunit: Algorithms and Complexity Group Audience: experts only Appearance: MPII WWW Server, MPII FTP Server, MPG publications list, university publications list, working group publication list, Fachbeirat, VG Wort

BibTeX Entry:

@INPROCEEDINGS{Leejhc2000,
AUTHOR = {Lee, Jae-Ha and Cheong, Otfried and Kwon, Woo-Cheol and Shin, Sung-Yong and Chwa, Kyung-Yong},
EDITOR = {Paterson, Mike},
TITLE = {Approximation of Curvature-constrained Shortest Paths through a Sequence of Points},
BOOKTITLE = {Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)},
PUBLISHER = {Springer},
YEAR = {2000},
TYPE = {Extended Abstract},
VOLUME = {1879},
PAGES = {314--325},
SERIES = {Lecture Notes in Computer Science},