Min-Max Multiple Fixed Watchman Routes in Minbar Polygons, with Non-domination Assumption

Subject Areas : Robotics

Rahmat Ghasemi ¹ , Alireza Bagheri ^{2 *} , Faezeh Farivar ³ , Fatemeh Keshavarz-kohjerdi ⁴

1 - Department of Computer and Mechatronics Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
2 - Department of Computer Engineering and Information Technology, Amirkabir University of Technology, Tehran, Iran
3 - Department of Computer and Mechatronics Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran
4 - Department of Computer Science, Shahed University, Tehran, Iran

Received: 2025-08-25 Accepted : 2025-10-26 Published : 2025-12-17

Keywords: Multiple watchman routes , Staircase polygons , Minbar polygons , Art gallery problem , Dynamic programming,

Abstract :

In this paper, the problem of multiple watchman routes in Minbar polygons\footnote{A minbar is a pulpit in a mosque where the imam (leader of prayers) stands to deliver sermons.} is studied, where every point in the given polygon must be visible from at least one point on some watchmen's route. The problem of multiple watchman routes is NP-hard even in simple polygons. However, some limited types of polygon have been shown to have polynomial-time solutions. We propose an algorithm based on the dynamic programming approach that requires \( O(n) \) space and consumes \( O(n \cdot \log(n)) \) time for min-max criterion, where \( n \) is the number of polygon vertices. We assume that the starting points of watchmen do not dominate each-other.

References:

[1] Mark de Berg, Otfried Cheong, Marc van Kreveld, and Mark Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag TELOS, Santa Clara, CA, USA, 3rd ed. edition, 2008.
[2] Ning Xu. On the watchman route problem and its related problems dissertation proposal. 2015.
[3] Bengt J. Nilsson and Eli Packer. An approximation algorithm for the two-watchman route in a simple polygon. In EuroCG 2016, 2016.
[4] Moshe Dror, Alon Efrat, Anna Lubiw, and Joseph S. B. Mitchell. Touring a sequence of polygons. In Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, STOC ’03, page 473–482, New York, NY, USA, 2003. Association for Computing Machinery.
[5] V. Černý. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. Journal of Optimization Theory and Applications, 45:41–51, 1985.
[6] Eli Packer. Computing multiple watchman routes. In Catherine C. McGeoch, editor, Experimental Algorithms, pages 114–128, Berlin, Heidelberg, 2008. Springer Berlin Heidelberg.
[7] Chapter 15 - geometric shortest paths and network optimization. In J.-R. Sack and J. Urrutia, editors, Handbook of Computational Geometry, pages 633–701. North-Holland, Amsterdam, 2000.
[8] A linear algorithm for computing the visibility polygon from a point. Journal of Algorithms, 2(2):186–197, 1981.
[9] Mireille Bousquet-Melou, Anthony J Guttmann, William P. Orrick, and Andrew Rechnitzer. Inversion relations, reciprocity and polyominoes. Annals of Combinatorics, 3:223–249, 1999.
[10] Optimum watchman routes. Information Processing Letters, 28(1):39 – 44, 1988.
[11] Adrian Dumitrescu and Csaba D. Tóth. Watchman tours for polygons with holes. Computational Geometry, 45(7):326 – 333, 2012.
[12] Wei-Pang Chin and Simeon Ntafos. Shortest watchman routes in simple polygons. Discrete & Computational Geometry, 6(1):9–31, Mar 1991.
[13] Bengt J. Nilsson and Derick Wood. Optimum watchmen routes in spiral polygons. In Proceedings of the Second Canadian Conference in Computational Geometry, pages 269–272, Ottawa, Ontario, 1990.
[14] Xuehou Tan and Bo Jiang. An improved algorithm for computing a shortest watchman route for lines. Information Processing Letters, 131:51 – 54, 2018.
[15] Improved exploration of unknown polygons. Theoretical Computer Science, 922:424–437, 2022.
8[16] B. J. Nilsson and S. Schuierer. Shortest m-watchmen routes for histograms: the minmax case. In Proceedings ICCI ‘92: Fourth International Conference on Computing and Information, pages 30–33, 1992.
[17] Alireza Bagheri, Anna Brötzner, Faezeh Farivar, Rahmat Ghasemi, Fatemeh Keshavarz-Kohjerdi, ErikKrohn, Bengt J. Nilsson, and Christiane Schmidt. Minsum m watchmen’s routes in Stiegl polygons. pages 41–44. XX Spanish Meeting on Computational Geometry, 2023.
[18] Rahmat Ghasemi, Alireza Bagheri, Fatemeh Keshavarz-Kohjerdi, and Faezeh Farivar. Fixed k-watchman routes under the min-max criterion in staircase polygons. AUT Journal of Mathematics and Computing, 2024.