06098086

j

06098086 Iwerks, Justin Mitchell, Joseph S.B. The art gallery theorem for simple polygons in terms of the number of reflex and convex vertices. Inf. Process. Lett. 112, No. 20, 778-782 (2012). 2012 Elsevier Sciences Publishers (North-Holland), Amsterdam EN computational geometry art gallery theorem visibility coverage guard number

doi:10.1016/j.ipl.2012.07.005

Summary: We present an art gallery theorem for simple polygons having $n$ vertices in terms of the number, $r$, of reflex vertices and the number, $c$, of convex vertices ($n=r+c$). Tight combinatorial bounds have previously been shown when $0\leq r\leq \lfloor\frac{c}{2}\rfloor$ and when $r\geq 5c - 12$. We give a lower bound construction that matches the $\lfloor\frac{n}{3}\rfloor$ sufficiency condition from the traditional art gallery theorem when $\lfloor\frac{c}{2}\rfloor