Guarding monotone art galleries with sliding cameras in linear time

A sliding camera in an orthogonal polygon P—that is, a polygon all of whose edges are axis-parallel—is a point guard g that travels back and forth along an axis-parallel line segment s inside P. A point p in P is guarded by g if and only if there exists a point q on s such that line segment pq is normal to s and contained in P. In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. 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.