MPI-INF Logo
Publications

Server    domino.mpi-inf.mpg.de

Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop

Author, Editor
Author(s):
Lee, Jae-Ha
Cheong, Otfried
Kwon, Woo-Cheol
Shin, Sung-Yong
Chwa, Kyung-Yong		dblp
dblp
dblp
dblp
dblp
Editor(s):
Paterson, Mikedblp
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:
28 March 2023
Event End Date:
28 March 2023
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:
Note, Abstract, ©
(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},
 ADDRESS = {Saarbr{\"u}cken,Germany},
 MONTH = {September},
}

Entry last modified by Uwe Brahm, 03/02/2010
Hide details for Edit History (please click the blue arrow to see the details)Edit History (please click the blue arrow to see the details)

Editor(s)
Jae Ha Lee		Created
02/21/2001 12:26:16
Revisions
6.
5.
4.
3.
2.		Editor(s)
Uwe Brahm
Uwe Brahm
Uwe Brahm
Anja Becker
Anja Becker		Edit Dates
05/02/2001 11:15:07 AM
04/09/2001 12:15:46 PM
04/04/2001 06:12:00 PM
20.03.2001 16:58:59
14.03.2001 13:01:08