A linear time 8/3-approximation for $r$-star guards in simple orthogonal art galleries

Abstract

We study the problem of covering simple orthogonal art galleries with rectangular stars. The problem has been shown to be polynomial by Worman and Keil, but to our knowledge, the exponent of the running time is still in the double digits. A linear-time 3-approximation algorithm using a partitioning into staircase shaped regions has been discovered by Lingas, Wasylewicz, and Żyliński. This is a follow-up paper to our recent theoretical result linking point guards to horizontal mobile guards and vertical mobile guards (vision is restricted to rectangular vision). The result of this paper is that the algorithm implicitly described by our theoretical result can in fact be run in linear time. The novelty of the approach is the sparse representation of the pixelation graph of simple orthogonal polygons and the heavy reliance on so-called horizontal and vertical $R$-trees. After translating the problem into graph theory, geometrical insight is barely needed to verify the correctness of the algorithm.