Parameter Analysis for Guarding Terrains
| Autor: | Akanksha Agrawal, Sudeshna Kolay, Meirav Zehavi |
|---|---|
| Rok vydání: | 2022 |
| Předmět: |
FPT Algorithm
Terrain Guarding General Computer Science Terrain Minima Applied Mathematics ComputerApplications_COMPUTERSINOTHERSYSTEMS Kernelization Computer Science::Computational Geometry XP Algorithm GeneralLiterature_MISCELLANEOUS ComputingMethodologies_COMPUTERGRAPHICS Reflex Vertices Computer Science Applications |
| Zdroj: | Algorithmica. 84:961-981 |
| ISSN: | 1432-0541 0178-4617 |
| Popis: | The Terrain Guarding problem is a well-known variant of the famous Art Gallery problem. Only second to Art Gallery, it is the most well-studied visibility problem in Discrete and Computational Geometry, which has also attracted attention from the viewpoint of Parameterized complexity. In this paper, we focus on the parameterized complexity of Terrain Guarding (both discrete and continuous) with respect to two natural parameters. First we show that, when parameterized by the number r of reflex vertices in the input terrain, the problem has a polynomial kernel. We also show that, when parameterized by the number c of minima in the terrain, Discrete Orthogonal Terrain Guarding has an XP algorithm. LIPIcs, Vol. 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020), pages 4:1-4:18 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full text from SpringerLink