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 that $\lfloor\frac{3n+4}{16}\rfloor$ mobile guards are sufficient to control the interior of an $n$-vertex orthogonal polygon.

Budapest, Hungary
Professor of Artificial Intelligence

My research interests include distributed robotics, mobile computing and programmable matter.