Mobile vs. point guards in orthogonal art gallery theorems

Abstract

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.

Date
Location
Budapest, Hungary
Avatar
Tamás Róbert Mezei
Mathematician

My research interests include Graph Theory, Computational Geometry, and Algorithms