The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS

Stephan Friedrichs, Michael Hemmer, James King +1

In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an $x$-monotone chain of line segments in ${\mathbb{R}}^2$ (the terrain $T$) and ask for the minimum number…