Polygon Exploration with Discrete Vision

Abstract

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.