Consider a sliding camera that travels back and forth along an orthogonal line segment s inside an orthogonal polygon P with n vertices. The camera can see a point p inside P if and only if there exists a line segment containing p that crosses s at a right angle and is completely contained in P. In the minimum sliding cameras (MSC) problem, the objective is to guard P with the minimum number of sliding cameras. In this paper, we give an O(n~(5/2))-time (7/2)-approximation algorithm to the MSC problem on any simple orthogonal polygon with n vertices, answering a question posed by Katz and Morgenstern (2011). To the best of our knowledge, this is the first constant-factor approximation algorithm for this problem.
展开▼
