Bootstrap percolation is a class of cellular automata with random initial state. Two-dimensional bootstrap percolation models have three universality classes, the most studied being the 'critical' one. For this class the scaling of the quantity of …
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 …