point guard

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

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 …

Mobile vs. point guards in orthogonal art gallery theorems

Our results are concerned with art gallery theorems on orthogonal polygons. We prove that an n-vertex orthogonal polygon can be partitioned into $\lfloor\frac{3n+4}{16}\rfloor$ at most 8-vertex pieces. This directly implies Aggarwal's theorem, namely …