We consider two variants of the classical Art Gallery Problem---one varying the environment to be guarded and one varying the capabilities of the guards.
In the continuous 1.5-dimensional terrain guarding problem we are given an x-monotone chain (the terrain $T$) and ask for the minimum number of point guards (located anywhere on $T$), such that all points of $T$ are covered by at least one guard. It has been shown that the 1.5-dimensional terrain guarding problem is NP-hard. The best known approximation algorithm achieved a factor of 4. For the discrete problem version with a finite set of guard candidates and a finite set of points on the terrain that need to be monitored, a polynomial time approximation scheme (PTAS) has been presented by Gibson et al.. We show that for the general problem we can construct finite guard and witness sets, $G$ and $W$, such that there exists an optimal guard cover $G^* \subseteq G$ that covers $T$, and when these guards monitor all points in $W$ the entire terrain is guarded. This leads to a PTAS as well as an (exact) IP formulation for the continuous terrain guarding problem. In addition, we significantly reduce the size of the constructed sets, allowing us to propose an algorithm for reliably finding exact, optimal solutions for instances 100000 vertices within seconds.
2-transmitters, opposed to the classical (0-transmitting) guards, can see through at most 2 polygon edges. We show it is NP-hard to compute a minimum cover of point 2-transmitters, point k-transmitters and edge 2-transmitters in a simple polygon; the point 2-transmitter result extends to orthogonal polygons. Moreover, we provide "Art Gallery Theorem"-like results, that is, necessity and sufficiency results, for edge 2-transmitters in various polygon classes: general, monotone, orthogonal and monotone, orthogonal polygons.
This is joint work with a) Stephan Friedrichs and Michael Hemmer and b) Sarah Cannon, Thomas Fai, Justin Iwerks and Undine Leopold.