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.

@InProceedings{fekete_et_al:DagSemProc.06421.8,
  author =	{Fekete, S\'{a}ndor and Schmidt, Christiane},
  title =	{{Polygon Exploration with Discrete Vision}},
  booktitle =	{Robot Navigation},
  pages =	{1--23},
  series =	{Dagstuhl Seminar Proceedings (DagSemProc)},
  ISSN =	{1862-4405},
  year =	{2007},
  volume =	{6421},
  editor =	{S\'{a}ndor Fekete and Rudolf Fleischer and Rolf Klein and Alejandro Lopez-Ortiz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2007/871},
  URN =		{urn:nbn:de:0030-drops-8714},
  doi =		{10.4230/DagSemProc.06421.8},
  annote =	{Keywords: Searching, scan cost, visibility problems, watchman problems, online searching, competitive strategies, autonomous mobile robots.}
}