MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
@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 – Ilya Bogdanov Sep 22 '15 at 9:38

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.