1.5D terrain guarding problem parameterized by guard range. (English) Zbl 1356.68088
Summary: The 1.5D terrain guarding problem examines a 1.5D terrain as an \(x\)-monotone polygonal chain in a plane to find the minimum guarding set for a given input terrain. This problem is NP-complete. In real world applications, guard power is limited and can only cover things within a range. Considering this limitation, the present study introduces the “terrain guard range” as a new geometric parameter by discretizing the definition of range, then presents a fixed-parameter algorithm to demonstrate that the 1.5D terrain guarding problem is fixed-parameter tractable with respect to the introduced parameter.
MSC:
| 68Q17 | Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) |
| 68U05 | Computer graphics; computational geometry (digital and algorithmic aspects) |
References:
| [1] | Ben-Moshe, Boaz; Katz, Matthew J.; Mitchell, Joseph S. B., A constant-factor approximation algorithm for optimal 1.5D terrain guarding, SIAM J. Comput., 36, 6, 1631-1647 (2007) · Zbl 1154.68569 |
| [2] | Chen, Danny Z.; Estivill-Castro, Vladimir; Urrutia, Jorge, Optimal guarding of polygons and monotone chains, (CCCG (1995), Citeseer), 133-138 |
| [3] | Clarkson, Kenneth L.; Varadarajan, Kasturi, Improved approximation algorithms for geometric set cover, Discrete Comput. Geom., 37, 1, 43-58 (2007) · Zbl 1106.68121 |
| [4] | Cygan, Marek; Fomin, Fedor V.; Kowalik, Łukasz; Lokshtanov, Daniel; Marx, Dániel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket, Parameterized Algorithms, vol. 4 (2015), Springer · Zbl 1334.90001 |
| [5] | Downey, Rod G.; Ralph, Michael, Fellows. Parameterized Complexity, vol. 3 (1999), Springer: Springer Heidelberg |
| [6] | Elbassioni, Khaled; Krohn, Erik; Matijević, Domagoj; Mestre, Julián; Ševerdija, Domagoj, Improved approximations for guarding 1.5-dimensional terrains, Algorithmica, 60, 2, 451-463 (2011) · Zbl 1215.68272 |
| [7] | Flum, Jörg; Grohe, Martin, Parameterized Complexity Theory, vol. 3 (2006), Springer · Zbl 1143.68016 |
| [8] | Kumar Ghosh, Subir, Visibility Algorithms in the Plane, vol. 2 (2007), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1149.68076 |
| [9] | Gibson, Matt; Kanade, Gaurav; Krohn, Erik; Varadarajan, Kasturi, An approximation scheme for terrain guarding, (Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (2009), Springer), 140-148 · Zbl 1255.68302 |
| [10] | Khodakarami, Farnoosh; Didehvar, Farzad; Mohades, Ali, A fixed-parameter algorithm for guarding 1.5D terrains, Theoret. Comput. Sci., 595, 130-142 (2015) · Zbl 1328.68262 |
| [11] | King, James, A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains (2006), Springer · Zbl 1145.68596 |
| [12] | King, James; Krohn, Erik, Terrain guarding is np-hard, SIAM J. Comput., 40, 5, 1316-1339 (2011) · Zbl 1235.68076 |
| [13] | Niedermeier, Rolf, Invitation to Fixed-Parameter Algorithms (2006), Oxford University Press · Zbl 1095.68038 |
| [14] | Niedermeier, Rolf, Reflections on multivariate algorithmics and problem parameterization, (27th International Symposium on Theoretical Aspects of Computer Science. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 (2010)), 17-32 · Zbl 1230.68096 |
| [15] | O’Rourke, Joseph, Art Gallery Theorems and Algorithms, vol. 57 (1987), Oxford University Press: Oxford University Press Oxford · Zbl 0653.52001 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
