# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Approximation of Curvature-constrained Shortest Paths through a Sequence of Points

##### Locator

There are no locators available

##### Fulltext (public)

There are no public fulltexts available

##### Supplementary Material (public)

There is no public supplementary material available

##### Citation

Lee, J.-H., Cheong, O., Kwon, W.-C., Shin, S.-Y., & Chwa, K.-Y. (2000). Approximation
of Curvature-constrained Shortest Paths through a Sequence of Points. In M. Paterson (*Algorithms - ESA 2000, Proceedings of the 8th Annual European Symposium (ESA-00)* (pp. 314-325).
Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-3382-5

##### 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.