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 …
We study the problem of guarding orthogonal art galleries with horizontal mobile guards (alternatively, vertical) and point guards, using "rectangular vision". We prove a sharp bound on the minimum number of point guards required to cover the gallery …
The thesis consists of two parts. In both parts, the problems studied are of significant interest, but are either _NP_-hard or unknown to be polynomially decidable. Realistically, this forces us to relax the objective of optimality or restrict the …
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 …
Art gallery theorems are concerned with the number of guards required to control a polygon, and many variations exist depending on how much power the guards have and what kind of restrictions are imposed on the polygon. Even though by nature these …
We prove that every simply connected orthogonal polygon of $n$ vertices can be partitioned into $\lfloor\frac{3n+4}{16}\rfloor$ (simply connected) orthogonal polygons of at most 8 vertices. It yields a new and shorter proof of the theorem of A. …