Approximation algorithms for the freeze tag problem inside polygons

Articles in Press

Document Type : Research Paper

Authors

1 Department of Computer Engineering, Iran University of Science and Technology, Tehran, Iran

2 Computer Engineering Department, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran

10.22108/toc.2025.143753.2229

Abstract

The freeze tag problem (FTP) aims to awaken a swarm of robots with one or more initially awake robots as soon as possible. Each awake robot must touch a sleeping robot to wake it up. Once a robot is awakened, it can assist in awakening other sleeping robots. We study this problem inside a polygonal domain and present approximation algorithms for it.

Keywords

Main Subjects

References

[1] Y. Z. A. Lubiw, The visibility freeze-tag problem, 24th annual fall workshop on computational geometry (FWCG), University of Connecticut, (2014).
[2] M. A. Abam, Spanners for geodesic graphs and visibility graphs, Algorithmica 80 no. 2 (2018) 515–529.
[3] Z. Abel, H. A. Akitaya and J. Yu, Freeze tag awakening in 2D is NP-hard, 27th 24th annual fall workshop on computational geometry (FWCG), Stony Brook University, Stony Brook, (2017).
[4] A. Ahadi and A. Zarei, Connecting guards with minimum steiner points inside simple polygons, Theoret. Comput. Sci., 775 (2019) 26–31.
[5] N. Ahuja, H. Bikkavilli, Z. Chen, M. M. Eshaghian-Wilner, A. Mittal, K. Ravicz, B. Sangal, S. Sarma, M. Schlesinger and A. Wilner, Real-time cellular-level imaging and medical treatment with a swarm of wireless multifunctional robots, J. Supercomput., 78 no. 1 (2022) 1923–1943.
[6] D. Albiero, A. P. Garcia, C. K. Umezu and R. L. de Paulo, Swarm robots in mechanized agricultural operations: A review about challenges for research, Comput. Electron. Agric., 193 (2022) p. 106608.
[7] E. Arkin, M. Bender, S. Fekete, J. Mitchell and M. Skutella, The freeze-tag problem: how to wake up a swarm of robots, Algorithmica, 46 no. 2 193–221.
[8] P. Bose, P. Morin, A. van Renssen and S. Verdonschot, The θ5 -graph is a spanner, Comput. Geom., 48 no. 2 (2015) 108–119.
[9] M. Gan, Q. Qian, D. Li, Y. Ai and X. Liu, Capturing the swarm intelligence in truckers: The foundation analysis for future swarm robotics in road freight, Swarm Evol. Comput., 62 (2021) p. 100845.
[10] P. A. Hoeher, J. Sticklus and A. Harlakin, Underwater optical wireless communications in swarm robotics: A tutorial, IEEE. Commun. Surv. Tutorials, 23 no. 4 (2021) 2630–2659.
[11] M. P. Johnson, Easier hardness for 3D freeze-tag, 27th annual fall workshop on computational geometry (FWCG), Stony Brook University, Stony Brook, (2017).
[12] Z. Moezkarimi and A. Bagheri, A PTAS for geometric 2-FTP, Inform. Process. Lett., 114 no. 12 (2014) 670–675.
[13] E. Osaba, J. Del Ser, A. Iglesias and X.-S. Yang, Soft computing for swarm robotics: New trends and applications, J. Comput. Sci., 39 (2020) p. 101049.
[14] M. Senanayake, I. Senthooran, J. C. Barca, H. Chung, J. Kamruzzaman and M. Murshed, Search and tracking algorithms for swarms of robots: A survey, Rob. Auton. Syst., 75 (2016) 422–434.
[15] M. O. Sztainberg, E. Arkin, M. Bender and J. Mitchell, Analysis of heuristics for the freeze-tag problem, Algorithm Theory–SWAT 2002, Lecture Notes in Comput. Sci., 2368, Springer, Berlin, 2002.
[16] Q. Tang, Z. Xu, F. Yu, Z. Zhang and J. Zhang, Dynamic target searching and tracking with swarm robots based on stigmergy mechanism, Rob. Auton. Syst., 120 (2019) p. 103251.
[17] A. van Renssen and G. Wong, Bounded-degree spanners in the presence of polygonal obstacle, Theor. Comput. Sci., 854 (2021) 159–173.
Transactions on Combinatorics

Articles in Press, Corrected Proof
Available Online from 11 November 2025

Files

History

  • Receive Date: 25 December 2024
  • Revise Date: 21 May 2025
  • Accept Date: 02 June 2025
  • Published Online: 11 November 2025

Share

How to cite

Statistics