5
$\begingroup$

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?

Improve this question
$\endgroup$
14
  • $\begingroup$ 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 $\endgroup$
    – David White
    Commented Jun 25, 2013 at 22:57
  • $\begingroup$ @Michael: how is a guard set (guarding set) defined? $\endgroup$
    – Włodzimierz Holsztyński
    Commented Jun 25, 2013 at 23:20
  • 2
    $\begingroup$ @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$. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 25, 2013 at 23:28
  • 4
    $\begingroup$ @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. $\endgroup$
    – Joseph O'Rourke
    Commented Jun 25, 2013 at 23:42
  • 1
    $\begingroup$ @domotorp: This is proved in epubs.siam.org/doi/abs/10.1137/0602042. $\endgroup$
    – Ilya Bogdanov
    Commented Sep 22, 2015 at 9:38

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .