<p>I'm not aware of any such work.  However, I would expect that such a problem would be NP-complete and, for polygons with holes, would be as hard to approximate as Set Cover.  The relatively straightforward vertex/vertex guarding problem, in which guards can only lie on vertices and only vertices need to be guarded, is this hard (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.9090">Eidenbenz, Stamm, and Widmayer (2001)</a>).</p>

<p>For simple polygons, I expect such a problem would be:</p>

<ul>
<li>NP-complete</li>
<li>APX-hard</li>
<li>Approximable to within a factor of $O(\log(\rm{opt}))$, where opt is the optimum number of guards.</li>
</ul>

<p>The vertex/vertex guarding problem is APX-hard for simple polygons (<a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.2653">Eidenbenz (1998)</a>).</p>

<p>The best algorithms for the art gallery problem for simple polygons are based on building small $\varepsilon$-nets.  In simple polygons, the range spaces induced by visibility polygons have constant VC-dimension.  Circles do as well.  Therefore a range space induced by visibility polygons in a simple polygon, circles, and the intersections and unions thereof, will also have constant VC-dimension and you can get a $O(\log(\rm{opt}))$-approximation algorithm.</p>

<p>I thought about this problem a little for my thesis, but came to the opinion that there weren't any particularly interesting variants that didn't seem to reduce fairly closely to a known problem involving single-guarding.</p>

CC BY-SA 3.0
2011-08-31T20:10:49.200Z
2011-08-31T20:10:49.200Z
James King
<p>Rather late to this question (sorry!).  There is at least a little bit of work.</p>

<p>(1) This appears to
be an undergrad (Swarthmore) research paper: 
"Optimal Double Coverage In The Art Gallery," 
Scott Dalane, Andrew Frampton, 2008,
<a href="http://www.cs.swarthmore.edu/~adanner/cs97/s08/papers/dalane_frampton.pdf">PDF link</a>.  From their conclusion:</p>

<blockquote>
  <p>After testing our algorithm on progressively more 
  complex polygons, our algorithm easily does better than $\lfloor 2n/3 \rfloor$ camera placement for double coverage of cameras outside of the the worst case, while 
  the entire program runs in $n^2$ time...</p>
</blockquote>

<p>(2) I also found a 2007 German Ph.D. thesis, "Facility Location and Related Problems,"
by Martin Romauch (<a href="http://othes.univie.ac.at/361/1/12-03-2007_9460262.pdf">PDF link</a>),
that includes a chapter on the "Vertex Guard Double Cover problem,"
showing that it is NP-hard for polygons with holes.
He also shows that the right combinatorial bound is $\lfloor 2n/3 \rfloor$
(disappointingly obvious!).  I have only skimmed through this, but it is certainly
worth a look.</p>

CC BY-SA 3.0
2011-09-21T21:51:45.107Z
So I've been thinking about this. I think the main difference between double coverage and my problem is that there's this "connectedness" issue. In other words, neither of the visibility regions of the two guards get activated unless they're "visible" to each other. It's easy to construct examples where you can double cover a region with guards that don't see each other. Now the connected guards problem has ALSO been looked at, but in a different context which again doesn't apply here - specifically there you require that the guard visibility graph is connected, and I don't need that.
Suresh Venkat
CC BY-SA 3.0
2011-09-21T23:17:59.543Z
@Suresh: So a point $p$ is covered iff there is a pair of guards who (a) can see one another and (b) both see $p$?  Just trying to understand the problem formulation...
Joseph O'Rourke
CC BY-SA 3.0
2011-09-21T23:34:53.507Z
Oh, and (c) both are "within range" of $p$?
Joseph O'Rourke
CC BY-SA 3.0
2011-09-22T04:44:03.677Z
Not quite. it's not pure visibility. A pair of guards defines a "region of visibility" and a point is covered if it lies in the region of visibility of the guards. It is in fact possible for guards that can't see each other OR the point in the traditional "line of sight" sense to "cover" the point.
Suresh Venkat
CC BY-SA 3.0
2011-09-22T09:55:57.993Z
Thanks for clarifying.  This model does seem different from anything I know.
Joseph O'Rourke
CC BY-SA 3.0
2011-09-22T16:00:26.913Z
That makes me feel a lot better. If you haven't heard of it, then it most likely doesn't exist yet :)
Suresh Venkat
CC BY-SA 3.0
2011-09-21T20:01:56.953Z
2011-09-21T20:01:56.953Z
Joseph O'Rourke
<p>The traditional <a href="http://en.wikipedia.org/wiki/Art_gallery_problem" rel="nofollow">art gallery problem</a> sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region.</p>

<p>Has anyone ever looked at art gallery variants where the visibility region is instead defined by a <strong>pair</strong> of guards. For example, one formulation might be that a point is covered if there's a pair of guards whose minimum bounding disk covers it ?</p>

CC BY-SA 3.0
2011-08-30T20:22:20.160Z
Quis custodiet ipsos custodes?
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-30T21:22:55.257Z
Well, to answer @Artem's question, there is a notion of *connected guards*, which has two variants.  Let the *visibility graph* be defined with a vertex for each guard, and an edge between two vertices if the guards can see each other.  If the visibility graph is connected, all the guards are guarded (sometimes called a "set of guarded guards").  A stronger condition is that the visibility graph have a single connected component.  Then you have a set of connected guards.  And yes, there is a fair amount of work here.  I've even blogged about one paper.
Aaron Sterling
CC BY-SA 3.0
2011-08-30T21:28:24.050Z
Whoops, the above should read "if the visibility graph has no isolated vertices, all the guards are guarded..."
Aaron Sterling
CC BY-SA 3.0
2011-08-30T22:36:55.367Z
"who guards the guards" ? my latin is only pig :)
Suresh Venkat
CC BY-SA 3.0
2011-08-30T22:39:08.420Z
Note that in my formulation, I don't require that the induced visibility graph be connected. While this might not be an issue with axis-parallel rectangles, it actually might be an issue with regions that aren't so nice (like elliptical regions). But the connected guards pointer is a good one: I think that probably some variants of my problem can be addressed that way.
Suresh Venkat
CC BY-SA 3.0
2011-08-31T01:09:39.880Z
@Suresh yeah, the more popular translation now-a-days is "who watches the watchmen", the question just reminded me of that and I meant it as a joke. However, if your guards are inside the gallery then each guard will have to be watched by at least one other guard (assuming some sort of natural visibility criterion like if a point is visible to both guards then it is visible to each guard). I think it is also important to have examples where the trivial process of placing two guards at each point you would normally place one guard produces a non-optimal solution
Artem Kaznatcheev
CC BY-SA 3.0
2011-08-31T01:50:06.927Z
@Artem: in general, an art gallery can be guarded by strictly fewer guards if they need not guard one another.
Aaron Sterling
CC BY-SA 3.0
2011-08-31T01:52:10.230Z
@Suresh: is your formulation equivalent to "visible from any point on a segment defined by these two endpoints"?
Aaron Sterling
CC BY-SA 3.0
2011-08-31T02:07:20.733Z
@Aaron its a subset because of range limits: ie I can't cover points that are too far away so visibility is limited.
Suresh Venkat
CC BY-SA 3.0
2011-08-31T02:38:32.200Z
That sounds more like a topology of sensor network coverage problem. Maybe this paper? http://dl.acm.org/citation.cfm?id=1147729  Ghrist has several in this vein.
Aaron Sterling
CC BY-SA 3.0
2011-08-31T03:36:20.883Z
It does involve objects like sensors as it turns out, but their characteristics are quite different from the usual sensor network settings.
Suresh Venkat
<reference-request><cg.comp-geom>
Art gallery variants with pairwise visibility?
Suresh Venkat
# Art gallery variants with pairwise visibility?

(Asked by: username_0 on 2011-08-30)

The traditional [art gallery problem](http://en.wikipedia.org/wiki/Art_gallery_problem) sets up a region and guards with some notion of visibility, and asks for the minimum number of guards that need to be placed to see the entire region.

Has anyone ever looked at art gallery variants where the visibility region is instead defined by a **pair** of guards. For example, one formulation might be that a point is covered if there's a pair of guards whose minimum bounding disk covers it ?

**Tags:** reference-request, cg.comp-geom
> **Comments:**
> **username_1**: Quis custodiet ipsos custodes?  
> **username_2**: Well, to answer @Artem's question, there is a notion of *connected guards*, which has two variants.  Let the *visibility graph* be defined with a vertex for each guard, and an edge between two vertices if the guards can see each other.  If the visibility graph is connected, all the guards are guarded (sometimes called a "set of guarded guards").  A stronger condition is that the visibility graph have a single connected component.  Then you have a set of connected guards.  And yes, there is a fair amount of work here.  I've even blogged about one paper.  
> **username_2**: Whoops, the above should read "if the visibility graph has no isolated vertices, all the guards are guarded..."  
> **username_0**: "who guards the guards" ? my latin is only pig :)  
> **username_0**: Note that in my formulation, I don't require that the induced visibility graph be connected. While this might not be an issue with axis-parallel rectangles, it actually might be an issue with regions that aren't so nice (like elliptical regions). But the connected guards pointer is a good one: I think that probably some variants of my problem can be addressed that way.  
> **username_1**: @Suresh yeah, the more popular translation now-a-days is "who watches the watchmen", the question just reminded me of that and I meant it as a joke. However, if your guards are inside the gallery then each guard will have to be watched by at least one other guard (assuming some sort of natural visibility criterion like if a point is visible to both guards then it is visible to each guard). I think it is also important to have examples where the trivial process of placing two guards at each point you would normally place one guard produces a non-optimal solution  
> **username_2**: @Artem: in general, an art gallery can be guarded by strictly fewer guards if they need not guard one another.  
> **username_2**: @Suresh: is your formulation equivalent to "visible from any point on a segment defined by these two endpoints"?  
> **username_0**: @Aaron its a subset because of range limits: ie I can't cover points that are too far away so visibility is limited.  
> **username_2**: That sounds more like a topology of sensor network coverage problem. Maybe this paper? http://dl.acm.org/citation.cfm?id=1147729  Ghrist has several in this vein.  
> **username_0**: It does involve objects like sensors as it turns out, but their characteristics are quite different from the usual sensor network settings.  

---

## 2 answers

### Answer by username_3 on 2011-08-31. Score: 5

I'm not aware of any such work. However, I would expect that such a problem would be NP-complete and, for polygons with holes, would be as hard to approximate as Set Cover. The relatively straightforward vertex/vertex guarding problem, in which guards can only lie on vertices and only vertices need to be guarded, is this hard ([Eidenbenz, Stamm, and Widmayer (2001)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.9090)).

For simple polygons, I expect such a problem would be:

* NP-complete
* APX-hard
* Approximable to within a factor of $O(\log(\rm{opt}))$, where opt is the optimum number of guards.

The vertex/vertex guarding problem is APX-hard for simple polygons ([Eidenbenz (1998)](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.39.2653)).

The best algorithms for the art gallery problem for simple polygons are based on building small $\varepsilon$-nets. In simple polygons, the range spaces induced by visibility polygons have constant VC-dimension. Circles do as well. Therefore a range space induced by visibility polygons in a simple polygon, circles, and the intersections and unions thereof, will also have constant VC-dimension and you can get a $O(\log(\rm{opt}))$-approximation algorithm.

I thought about this problem a little for my thesis, but came to the opinion that there weren't any particularly interesting variants that didn't seem to reduce fairly closely to a known problem involving single-guarding.


---

### Answer by username_4 on 2011-09-21. Score: 5

Rather late to this question (sorry!). There is at least a little bit of work.

(1) This appears to
be an undergrad (Swarthmore) research paper:
"Optimal Double Coverage In The Art Gallery,"
Scott Dalane, Andrew Frampton, 2008,
[PDF link](http://www.cs.swarthmore.edu/~adanner/cs97/s08/papers/dalane_frampton.pdf). From their conclusion:

> After testing our algorithm on progressively more
> complex polygons, our algorithm easily does better than $\lfloor 2n/3 \rfloor$ camera placement for double coverage of cameras outside of the the worst case, while
> the entire program runs in $n^2$ time...

(2) I also found a 2007 German Ph.D. thesis, "Facility Location and Related Problems,"
by Martin Romauch ([PDF link](http://othes.univie.ac.at/361/1/12-03-2007_9460262.pdf)),
that includes a chapter on the "Vertex Guard Double Cover problem,"
showing that it is NP-hard for polygons with holes.
He also shows that the right combinatorial bound is $\lfloor 2n/3 \rfloor$
(disappointingly obvious!). I have only skimmed through this, but it is certainly
worth a look.

> **Comments:**
> **username_0**: So I've been thinking about this. I think the main difference between double coverage and my problem is that there's this "connectedness" issue. In other words, neither of the visibility regions of the two guards get activated unless they're "visible" to each other. It's easy to construct examples where you can double cover a region with guards that don't see each other. Now the connected guards problem has ALSO been looked at, but in a different context which again doesn't apply here - specifically there you require that the guard visibility graph is connected, and I don't need that.  
> **username_4**: @Suresh: So a point $p$ is covered iff there is a pair of guards who (a) can see one another and (b) both see $p$?  Just trying to understand the problem formulation...  
> **username_4**: Oh, and (c) both are "within range" of $p$?  
> **username_0**: Not quite. it's not pure visibility. A pair of guards defines a "region of visibility" and a point is covered if it lies in the region of visibility of the guards. It is in fact possible for guards that can't see each other OR the point in the traditional "line of sight" sense to "cover" the point.  
> **username_4**: Thanks for clarifying.  This model does seem different from anything I know.  
> **username_0**: That makes me feel a lot better. If you haven't heard of it, then it most likely doesn't exist yet :)  

---

