An Optimal Algorithm for Geodesic Mutual Visibility on Hexagonal Grids

For a set of robots (or agents) moving in a graph, two properties are highly desirable: confidentiality (i.e., a message between two agents must not pass through any intermediate agent) and efficiency (i.e., messages are delivered through shortest paths). These properties can be obtained if the Geodesic Mutual Visibility (GMV) problem is solved: oblivious robots move along the edges of the graph, without collisions, to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. In this work, we optimally solve GMV on finite hexagonal grids Gk. This, in turn, requires first solving a graph combinatorial problem, i.e. determining the maximum number of mutually visible vertices in Gk.