New Hardness Results for Guarding Orthogonal Polygons with Sliding Cameras

Abstract

Let $P$ be an orthogonal polygon. Consider a sliding camera that travels back and forth along an orthogonal line segment $s\in P$ as its \emph{trajectory}. The camera can see a point $p\in P$ if there exists a point $q\in s$ such that $pq$ is a line segment normal to $s$ that is completely inside $P$. In the \emph{minimum-cardinality sliding cameras 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) while in the \emph{minimum-length sliding cameras 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. In this paper, we first settle the complexity of the minimum-length sliding cameras problem by showing that it is polynomial tractable even for orthogonal polygons with holes, answering a question asked by Katz and Morgenstern (2011). We next show that the minimum-cardinality sliding cameras problem is \textsc{NP}-hard when $P$ is allowed to have holes, which partially answers another question asked by Katz and Morgenstern (2011).

12 pages