Covering Orthogonal Polygons with Sliding k-Transmitters.
Salma Sadat Mahdavi, Saeed Seddighin, Mohammad Ghodsi · Canadian Conference on Computational Geometry · 2014
Abstract In this paper, we consider a new variant of covering in an orthogonal art gallery problem where each guard is a sliding k-transmitter. Such a guard can travel back and forth along an orthogonal line segment, say s, inside the polygon. A point p is covered by this guard if there exists a point q ∈ s such that p q ‾ is a line segment normal to s, and has at most k intersections with the boundary walls of the polygon. The objective is to minimize the sum of the lengths of the sliding k-transmitters to cover the entire polygon. In other words, the goal is to find the minimum total length of trajectories on which the guards can travel to cover the entire polygon. We prove that this problem is NP-hard when k = 2 , and present a 2-approximation algorithm for any fixed k ≥ 2 . The proposed algorithm also works well for an orthogonal polygon where the edges have thickness.