Change search
ReferencesLink to record
Permanent link

Direct link
The continuous 1.5D terrain guarding problem: Discretization, optimal solutions, and PTAS
Max Planck Institute for Informatics, Germany /Saarbrucken Graduate School of Computer Science.
TU Braunschweig, IBR, Algorithms Group, Braunschweig, Germany.
D-Wave Systems, Burnaby, Canada.
Linköping University, Department of Science and Technology, Communications and Transport Systems. Linköping University, Faculty of Science & Engineering.
2016 (English)In: Journal of Computational Geometry, ISSN 1920-180X, E-ISSN 1920-180X, Vol. 7, no 1, 256-284 p.Article in journal (Refereed) Published
Abstract [en]

In the NP-hard continuous 1.5D Terrain Guarding Problem (TGP) we are given an xx-monotone chain of line segments in R2 (the terrain TT), and ask for the minimum number of guards (located anywhere on TT) required to guard all of TT. We construct guard candidate and witness sets G,W⊂T of polynomial size such that any feasible (optimal) guard cover G∗⊆Gfor WW 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 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 10^6 vertices within minutes on a standard desktop computer.

Place, publisher, year, edition, pages
2016. Vol. 7, no 1, 256-284 p.
National Category
Computer Science
URN: urn:nbn:se:liu:diva-128646OAI: diva2:931015
Available from: 2016-05-26 Created: 2016-05-26 Last updated: 2016-06-13Bibliographically approved

Open Access in DiVA

fulltext(702 kB)14 downloads
File information
File name FULLTEXT01.pdfFile size 702 kBChecksum SHA-512
Type fulltextMimetype application/pdf

Other links


Search in DiVA

By author/editor
Schmidt, Christiane
By organisation
Communications and Transport SystemsFaculty of Science & Engineering
In the same journal
Journal of Computational Geometry
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 14 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Total: 290 hits
ReferencesLink to record
Permanent link

Direct link