How simple robots benefit from looking back: reconstructing visibility graphs of polygons

Abstract

We study the sensor and movement capabilities that simple robots need in order to create a map of an unknown polygon of size n, and to meet. We consider robots that can move from vertex to vertex, can backtrack movements, and see distant vertices in counter-clockwise order but have no means of visibly identifying them. We show that such robots can always solve the weak rendezvous problem and reconstruct the visibility graph, given an upper bound on n. Our results are tight: The strong rendezvous problem, in which robots need to gather at a common location, cannot be solved in general, and without a bound on n, not even n can be determined. In terms of mobile agents exploring a graph, our result implies that they can reconstruct any graph that is the visibility graph of a simple polygon. This is in contrast to the known result that the reconstruction of arbitrary graphs is impossible in general, even if n is known.