Item

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.