  Persistent monitoring missions require an up-to-date knowledge of the
changing state of the underlying environment. UAVs can be gainfully employed to
continually visit a set of targets representing tasks (and locations) in the
environment and collect data therein for long time periods. The enduring nature
of these missions requires the UAV to be regularly recharged at a service
station. In this paper, we consider the case in which the service station is
not co-located with any of the targets. An efficient monitoring requires the
revisit time, defined as the maximum of the time elapsed between successive
revisits to targets, to be minimized. Here, we consider the problem of
determining UAV routes that lead to the minimum revisit time. The problem is
NP-hard, and its computational difficulty increases with the fuel capacity of
the UAV. We develop an algorithm to construct near-optimal solutions to the
problem quickly, when the fuel capacity exceeds a threshold. We also develop
lower bounds to the optimal revisit time and use these bounds to demonstrate
(through numerical simulations) that the constructed solutions are, on an
average, at most 0.01% away from the optimum.
