Home News About Us Contact Contributors Disclaimer Help FAQ

 Display Documents

ID: 518131.0, MPI für Informatik / Algorithms and Complexity Group
Approximation of Curvature-constrained Shortest Paths through a Sequence of Points
Authors:
Language:English
Publisher:Springer
Place of Publication:Berlin, Germany
Date of Publication (YYYY-MM-DD):2000
Title of Proceedings:Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)
Start Page:314
End Page:325
Title of Series:Lecture Notes in Computer Science
Place of Conference/Meeting:Saarbrücken,Germany
(Start) Date of Conference/Meeting
(YYYY-MM-DD):
2000
Audience:Experts Only
Intended Educational Use:No
Abstract / Description: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.
Last Change of the Resource (YYYY-MM-DD):2010-03-02
External Publication Status:published
Document Type:Conference-Paper
Communicated by:Kurt Mehlhorn
Affiliations:
Identifiers:LOCALID:C1256428004B93B8-8CFC6B3E07DEFA8BC12569FA003ED4B1-...
 The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.