On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth
Saeed Mehrabi
Carleton University
There are 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 most $k$ bends. In this talk, I discuss these guarding models for the special case of orthogonal polygons that have bounded treewidth in some sense, and show that the problem of finding the minimum number of guards in all these models becomes linear-time solvable on polygons with bounded treewidth.
This is a joint work with Therese Biedl.