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

Document Type : Original Article

Authors

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

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

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

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

Main Subjects

AUT Journal of Mathematics and Computing

Articles in Press, Accepted Manuscript
Available Online from 11 September 2024

Files

Share

How to cite

Statistics