Amirkabir University of Technology AUT Journal of Mathematics and Computing 2783-2449 7 3 2026 07 01 Fixed k-watchman routes under the Min-Max criterion in staircase polygons 271 282 5536 10.22060/ajmc.2024.23104.1228 EN Rahmat Ghasemi Department of Computer Engineering, SR.C., Islamic Azad University, Tehran, Iran 0000-0001-8116-5234 Alireza Bagheri Department of Computer Engineering, Amirkabir University of Technology (Tehran Polytechnic), Tehran, Iran 0000-0002-3542-7763 Fatemeh Keshavarz-Kohjerdi Department of Computer Science, Shahed University, Tehran, Iran 0000-0002-7006-2675 Faezeh Farivar Department of Computer Engineering, SR.C., Islamic Azad University, Tehran, Iran Journal Article 2024 04 18 In this paper, the problem of multiple watchman routes in staircase polygons is studied. The watchman route problem (WRP) is a variation of the art gallery problem (AGP) in computational geometry, where each point in the given polygon must be visible from at least one point along the route taken by one of the watchmen. A greedy algorithm is presented for the min-max criterion, where we minimize the maximum route length. We assume some starting points of the watchmen may dominate the others. This algorithm finds an optimal solution in $O(n^2 \cdot k^2 \cdot \log{n})$ time, where $n$ represents the number of vertices of the give polygon, and $k$ represents the number of watchmen. Multiple watchman routes Orthogonal polygon Staircase polygon Min-max criterion Fixed watchman route https://ajmc.aut.ac.ir/article_5536_1134ac57b5b1d38b7d70c1b6feaa28cf.pdf