Abstract
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 (\(\mathrm {\ensuremath {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 \(\mathrm {\ensuremath {GMV}}\) on finite hexagonal grids \(G_k\). This, in turn, requires first solving a graph combinatorial problem, i.e. determining the maximum number of mutually visible vertices in \(G_k\).
The work has been partially supported by the European Union - NextGenerationEU under the Italian Ministry of University and Research (MUR) National Innovation Ecosystem grant ECS00000041-VITALITY—CUP E13C22001060006, SICURA—CUP C19C200005200004 and by the Italian National Group for Scientific Computation (GNCS-INdAM).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adhikary, R., Bose, K., Kundu, M.K., Sau, B.: Mutual visibility by asynchronous robots on infinite grid. In: Algorithms for Sensor Systems—ALGOSENSORS 2018. LNCS, vol. 11410, pp. 83–101. Springer (2018). https://doi.org/10.1007/978-3-030-14094-6_6
Bose, K., Adhikary, R., Kundu, M.K., Sau, B.: Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. Theor. Comput. Sci. 815, 213–227 (202https://doi.org/10.1016/J.TCS.2020.02.016
Brešar, B., Yero, I.G.: Lower (total) mutual-visibility number in graphs. Appl. Math. Comput. 465, 128411 (2024). https://doi.org/10.1016/j.amc.2023.128411
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: Arbitrary pattern formation on infinite regular tessellation graphs. Theor. Comput. Sci. 942, 1–20 (2023https://doi.org/10.1016/j.tcs.2022.11.021
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: The geodesic mutual visibility problem for oblivious robots: the case of trees. In: 24th International Conference on Distributed Computing and Networking, ICDCN 2023, pp. 150–159. ACM (2023). https://doi.org/10.1145/3571306.3571401
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: The geodesic mutual visibility problem: Oblivious robots on grids and trees. Pervasive Mob. Comput. 95, 101842 (2023). https://doi.org/10.1016/j.pmcj.2023.101842
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: Time-optimal geodesic mutual visibility of robots on grids within minimum area. In: Proceedings of the Stabilization, Safety, and Security of Distributed Systems, pp. 385–399. Springer (2023). https://doi.org/10.1007/978-3-031-44274-2_29
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A., Piselli, F.: Mutual Visibility in Hypercube-Like Graphs. In: Structural Information and Communication Complexity—SIROCCO 2024. LNCS, vol. 14662, pp. 192–207. Springer (2024). https://doi.org/10.1007/978-3-031-60603-8_11
Cicerone, S., Di Stefano, G.: Mutual-visibility in distance-hereditary graphs: a linear-time algorithm. Procedia Comput. Sci. 223, 104–111 (2023). https://doi.org/10.1016/J.PROCS.2023.08.219
Cicerone, S., Di Stefano, G., Klavžar, S.: On the mutual visibility in cartesian products and triangle-free graphs. Appl. Math. Comput. 438, 127619 (2023). https://doi.org/10.1016/j.amc.2022.127619
Cicerone, S., Di Stefano, G., Navarra, A.: A structured methodology for designing distributed algorithms for mobile entities. Inform. Sci. 574, 111–132 (2021). https://doi.org/10.1016/j.ins.2021.05.043
Cicerone, S., Di Stefano, G., Klavžar, S., Yero, I.G.: Mutual-visibility problems on graphs of diameter two. Eur. J. Combinatorics 120 (2024). https://doi.org/10.1016/j.ejc.2024.103995
Daymude, J.J., Hinnenthal, K., Richa, A.W., Scheideler, C.: Computing by programmable particles. In: Distributed Computing by Mobile Entities, Current Research in Moving and Computing, LNCS, vol. 11340, pp. 615–681. Springer (2019). https://doi.org/10.1007/978-3-030-11072-7_22
Di Luna, G.A., Flocchini, P., Chaudhuri, S.G., Poloni, F., Santoro, N., Viglietta, G.: Mutual visibility by luminous robots without collisions. Inf. Comput. 254, 392–418 (2017)
Di Stefano, G.: Mutual visibility in graphs. Appl. Math. Comput. 419, 126850 (2022). https://doi.org/10.1016/j.amc.2021.126850
Dudeney, H.E.: Amusements in Mathematics. Nelson, Edinburgh (1917)
Flocchini, P., Prencipe, G., Santoro, N.: Moving and computing models: robots. In: Distributed Computing by Mobile Entities, Current Research in Moving and Computing, LNCS, vol. 11340, pp. 3–14. Springer (2019).https://doi.org/10.1007/978-3-030-11072-7_1
Ghosh, S., Goswami, P., Sharma, A., Sau, B.: Move optimal and time optimal arbitrary pattern formations by asynchronous robots on infinite grid. Int. J. Parallel Emerg. Distrib. Syst. 38(1), 35–57 (2023). https://doi.org/10.1080/17445760.2022.2124411
Manuel, P., Klavžar, S.: A general position problem in graph theory. Bull. Aust. Math. Soc. 98(2), 177–187 (2018). https://doi.org/10.1017/S0004972718000473
Roy, D., Klavžar, S., Lakshmanan, A.: Mutual-visibility and general position in double graphs and in mycielskians. CoRR abs/2403.05120 (2024).https://doi.org/10.48550/arXiv.2403.05120
Wolfram MathWorld: Hexagonal Grid Graph. https://mathworld.wolfram.com/HexagonalGridGraph.html (2023) [Online; Entries Last Updated: Sat Jul 29 2023]
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Badri, S., Cicerone, S., Di Fonso, A., Di Stefano, G. (2025). An Optimal Algorithm for Geodesic Mutual Visibility on Hexagonal Grids. In: Masuzawa, T., Katayama, Y., Kakugawa, H., Nakamura, J., Kim, Y. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2024. Lecture Notes in Computer Science, vol 14931. Springer, Cham. https://doi.org/10.1007/978-3-031-74498-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-031-74498-3_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-74497-6
Online ISBN: 978-3-031-74498-3
eBook Packages: Computer ScienceComputer Science (R0)