On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth

There exist many variants of guarding an orthogonal polygon in an orthogonal fashion: sometimes a guard can see within a rectangle, along a staircase, or along an orthogonal path with at mostkbends. In this paper, we study all these guarding models for the special case of orthogonal polygons that have bounded treewidth in some sense. As our main result, we show that the problem of finding the minimum number of guards in all these models becomes linear-time solvable on polygons with bounded treewidth. We complement our main result by giving some hardness results.