Guarding monotone art galleries with sliding cameras in linear time

We give a dynamic programming algorithm that solves the MSC problem exactly on monotone orthogonal polygons in O(n) time, improving the 2-approximation algorithm of Katz and Morgenstern (2011). More generally, our algorithm can be used to solve the MSC problem in O(n) time on simple orthogonal polygons P for which the dual graph induced by the vertical decomposition of P is a path. Our results provide the first polynomial-time exact algorithms for the MSC problem on a non-trivial subclass of orthogonal polygons.