Art gallery variants with pairwise visibility? The traditional 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 ?
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)).

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)).

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.