Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
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
Thank you, @Joseph. Does it mean that $P$ is homeomorphic to a circle? Is the notion of "guarding" just--so to speak-- a little more general than of "seeing"? Are witnesses supposed to be inside the polygon (like visitors to a museum)? I guess it's time for me to check wikipedia or somethin' :-) –  Włodzimierz Holsztyński Jun 25 '13 at 23:38
@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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.