The Gate-Cover Problem
摘要
We introduce a new variant of the art gallery problem, namely, the Gate-Cover Problem for thin polyominoes. The problem is equivalently formulated as guarding streets in a city by placing cameras in (some) intersections. We study two variants - of bounded and unbounded range of visibility. We show that both variants are NP-hard, the unbounded variant even for polyominoes in which all junctions are T-junctions. In the case of bounded-range visibility we observe that the problem admits a PTAS, and for the unbounded variant we present a polynomial time 2-approximation algorithm. However, our experimental results indicate that the geometric setting may allow for a better approximation ratio. In particular, the greedy algorithm yields \(\ll 1.5\) -approximate results for randomly generated instances. Though we construct examples of instances for which the guaranteed approximation ratio of the greedy algorithm is not better than \(2-\varepsilon \) , we raise the question if more sophisticated tie-breaking rules may result in a provably better performance.