A competitive strategy for learning a polygon
Frank Hoffmann, Christian Icking, Rolf Klein, Klaus Kriegel · Symposium on Discrete Algorithms · 1997
We provide a competitive strategy for a mobile robot with vision, that has to explore an unknown simple polygon starting from and returning to a given point on the boundary. Our strategy creates a tour that does not exceed in length 133 times the length of the optimal watchman route. This paper is the first to describe a complete strategy and to give a proof for such a constant competitive factor.