Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons

Ghasemi, Rahmat; Bagheri, Alireza; Keshavarz-Kohjerdi, Fatemeh; Farivar, Faezeh

doi:10.22060/ajmc.2024.23104.1228

Fixed $k$-watchman routes under the Min-Max criterion in staircase polygons

Articles in Press

Document Type : Original Article

Authors

Rahmat Ghasemi ¹

Alireza Bagheri ²

Fatemeh Keshavarz-Kohjerdi ³

Faezeh Farivar ¹

¹ Department of Computer and Mechatronics Engineering, Science and Research Branch, Islamic Azad University, Tehran, Iran

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

³ Department of Computer Science, Shahed University, Tehran, Iran

10.22060/ajmc.2024.23104.1228

Abstract

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 of a route of a watchman. A greedy algorithm is presented for the min-max criterion, where we minimize the maximum route length. We assume that the watchmen's starting points may dominate eachother. This algorithm finds an optimal solution in $O(n^2 \cdot k^2 \cdot \log{n})$ time, where $n$ is the number of vertices and $k$ is the number of watchmen.

Keywords

Multiple watchman routes

Orthogonal polygon

Staircase polygon

Min-max criterion

Fixed watchman route

Subjects