@online{FriedrichsHemmerSchmidt2015,
TITLE = {The Continuous 1.5{D} Terrain Guarding Problem: {D}iscretization, Optimal Solutions, and {PTAS}},
AUTHOR = {Friedrichs, Stephan and Hemmer, Michael and King, James and Schmidt, Christiane},
LANGUAGE = {eng},
URL = {http://arxiv.org/abs/1509.08285},
EPRINT = {1509.08285},
EPRINTTYPE = {arXiv},
YEAR = {2015},
ABSTRACT = {In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an x-monotone chain of line segments in the plain (the terrain $T$), and ask for the minimum number of guards (located anywhere on $T$) required to guard all of $T$. We construct guard candidate and witness sets $G, W \subset T$ of polynomial size, such that any feasible (optimal) guard cover $G' \subseteq G$ for $W$ is also feasible (optimal) for the continuous TGP. This discretization allows us to: (1) settle NP-completeness for the continuous TGP; (2) provide a Polynomial Time Approximation Scheme (PTAS) for the continuous TGP using the existing PTAS for the discrete TGP by Gibson et al.; (3) formulate the continuous TGP as an Integer Linear Program (IP). Furthermore, we propose several filtering techniques reducing the size of our discretization, allowing us to devise an efficient IP-based algorithm that reliably provides optimal guard placements for terrains with up to 1000000 vertices within minutes on a standard desktop computer.},
}