# Guarding Variants: Continuous 1.5D Terrain Guarding and (Edge)
2-Transmitter Cover

## Christiane Schmidt, UNI

## February 3, 2015

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.