2026-08-16T16:20:30Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:871 2024-03-06T11:07:07Z ddc:004 open_access

Polygon Exploration with Discrete Vision Fekete, Sándor Schmidt, Christiane Searching scan cost visibility problems watchman problems online searching competitive strategies autonomous mobile robots. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sándor Fekete and Christiane Schmidt 2007 Is Part Of Dagstuhl Seminar Proceedings, Volume 6421, Robot Navigation (2007) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagSemProc.06421.8 urn:nbn:de:0030-drops-8714 https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06421.8 eng https://creativecommons.org/licenses/by/4.0/legalcode