Proceedings Article, Paper
@InProceedings
Beitrag in Tagungsband, Workshop
Show entries of:
this year
(2019) |
last year
(2018) |
two years ago
(2017) |
Notes URL
Action:
login to update
Options:
Goto entry point
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, 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
URL of the conference:
http://www.mpi-sb.mpg.de/~conf2000/esa2000/
URL for downloading the paper:
Event Address*:
Saarbrücken,Germany
Language:
English
Event Date*
(no longer used):
September,5 - September,8
Organization:
Event Start Date:
15 December 2019
Event End Date:
15 December 2019
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
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 PM
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