Polygon Exploration with Discrete Vision

With the advent of autonomous robots with two- and three-dimensional scanning capabilities, classical visibility-based exploration methods from computational geometry have gained in practical importance. However, real-life laser scanning of useful accuracy does not allow the robot to scan continuously while in motion; instead, it has to stop each time it surveys its environment. This requirement was studied by Fekete, Klein and N"uchter for the subproblem of looking around a corner, but until now has not been considered for whole polygonal regions. We give the first comprehensive algorithmic study for this important algorithmic problem that combines stationary art gallery-type aspects with watchman-type issues in an online scenario. We show that there is a lower bound of $Omega(sqrt{n})$ on the competitive ratio in an orthogonal polygon with holes; we also demonstrate that even for orthoconvex polygons, a competitive strategy can only be achieved for limited aspect ratio $A$, i.e., for a given lower bound on the size of an edge. Our main result is an $O(log A)$-competitive strategy for simple rectilinear polygons, which is best possible up to constants.