Guarding orthogonal art galleries with sliding cameras

摘要

Let P be an orthogonal polygon with n vertices. A sliding camera travels back and forth along an orthogonal line segment s subset of P corresponding to its trajectory. The camera sees a point p is an element of P if there is a point q is an element of s such that (pq) over bar is a line segment normal to s that is completely contained in P. In the Minimum-Cardinality Sliding Cameras (MCSC) problem, the objective is to find a set S of sliding cameras of minimum cardinality to guard P (i.e., every point in P can be seen by some sliding camera in S), while in the Minimum-Length Sliding Cameras (MLSC) problem the goal is to find such a set S so as to minimize the total length of trajectories along which the cameras in S travel.