# Upper bounds on art gallery problems using independent witnesses

Given a polygon $P$, the art gallery problem looks to find a smallest set of points that sees all of $P$. One way of bounding the number of guards necessary (from below) is to find a largest set of independent witness points, which are points whose visibility polygons are pairwise disjoint. Say the size of the smallest guarding set is $G(P)$ and the size of the largest witness set is $W(P)$. Then we have the trivial lower bound on $G(P)$, that $W(P) \leq G(P)$.

In arbitrary polygons, the size of the witness set does not help much with respect to an upper bound on the size of the guard set, i.e. there are examples with $\frac{G(P)}{W(P)} = \Omega(n)$.

Does the same hold for orthogonal polygons? It seems plausible to me that, unlike general polygons, a constant factor bound exists (maybe $\frac{G(P)}{W(P)} \leq 2$?), but my literature search came up empty. Can anyone point me at a reference, or a bad example?

• I don't know much about this problem, but does the work of Steve Fisk apply in your setting? I believe he got very nice bounds for his version of this problem – David White Jun 25 '13 at 22:57
• @Michael: how is a guard set (guarding set) defined? – Włodzimierz Holsztyński Jun 25 '13 at 23:20
• @Wlodzimierz: a guard set is a set of points such that every point in $P$ is connected to some point in the set by a segment that is nowhere exterior to $P$. – Joseph O'Rourke Jun 25 '13 at 23:28
• @Wlodzimierz: Yes, a simple polygon $P$ is homeomorphic to a disk. Yes, the guards are inside $P$ (or on its boundary). Yes, there is a Wikipedia page on art gallery theorems. – Joseph O'Rourke Jun 25 '13 at 23:42
• @domotorp: This is proved in epubs.siam.org/doi/abs/10.1137/0602042. – Ilya Bogdanov Sep 22 '15 at 9:38