English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse
  1. View item / 
  2. Item Summary

Item

ITEM ACTIONSEXPORT
Add to Basket
  Local TagsRelease HistoryDetailsSummary

Released
Paper

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

MPS-Authors
/persons/resource/persons135692

Friedrichs,  Stephan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1509.08285.pdf
(Preprint), 643KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Friedrichs, S., Hemmer, M., King, J., & Schmidt, C. (2015). The Continuous 1.5D Terrain Guarding Problem: Discretization, Optimal Solutions, and PTAS. Retrieved from http://arxiv.org/abs/1509.08285.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0029-4A50-8
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.