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
Friday, May 19, 2017
14:25 — 14:45
Location
Budapest, Hungary
Links