\input zb-basic
\input zb-ioport
\iteman{io-port 06098086}
\itemau{Iwerks, Justin; Mitchell, Joseph S.B.}
\itemti{The art gallery theorem for simple polygons in terms of the number of reflex and convex vertices.}
\itemso{Inf. Process. Lett. 112, No. 20, 778-782 (2012).}
\itemab
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<r<5c-12$, thereby providing tight combinatorial bounds for all $r$ and $c\geq 3$.
\itemrv{~}
\itemcc{}
\itemut{computational geometry; art gallery theorem; visibility coverage; guard number}
\itemli{doi:10.1016/j.ipl.2012.07.005}
\end