The Geodesic Mutual Visibility Problem for Oblivious Robots: the case of Trees

摘要

The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. Here we introduce the Geodesic Mutual Visibility problem, a possible counterpart for robots moving in a discrete environment. For a set of robots disposed on the vertices of a graph, it asks for moving the robots so that they are pairwise geodesic mutually visible, that is there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside.