Paper Info
Title
On Orthogonally Guarding Orthogonal Polygons With Bounded Treewidth
Abstract
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.
Year
DOI
Venue
2021
10.1007/s00453-020-00769-5
ALGORITHMICA
Keywords
DocType
Volume
Art gallery problem, Orthogonal polygons, Treewidth
Journal
83
Issue
ISSN
Citations 
2
0178-4617
0
PageRank 
References 
Authors
0.34
0
2
Name
Order
Citations
PageRank
Therese Biedl1902106.36
Saeed Mehrabi 00012287.00