Parameterized Analysis of Art Gallery and Terrain Guarding
From MaRDI portal
Publication:5042224
DOI10.1007/978-3-030-50026-9_2OpenAlexW3035901889MaRDI QIDQ5042224
Akanksha Agrawal, Meirav Zehavi
Publication date: 19 October 2022
Published in: Computer Science – Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-030-50026-9_2
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Fundamentals of parameterized complexity
- A new upper bound for the VC-dimension of visibility regions
- Improved approximations for guarding 1.5-dimensional terrains
- Improved approximation for guarding simple galleries from the perimeter
- Guarding galleries and terrains
- Improved approximation algorithms for geometric set cover
- Approximation algorithms for art gallery problems in polygons
- A short proof of Chvatal's Watchman Theorem
- Guarding galleries where no point sees a small area.
- Guarding galleries where every point sees a large area
- A combinatorial theorem in plane geometry
- Visibility graphs of staircase polygons and the weak Bruhat order. I: From visibility graphs to maximal chains
- Almost optimal set covers in finite VC-dimension
- Fast vertex guarding for polygons with and without holes
- Parameter analysis for guarding terrains
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- A fixed-parameter algorithm for guarding 1.5D terrains
- Approximability of guarding weak visibility polygons
- Approximate guarding of monotone and rectilinear polygons
- On guarding the vertices of rectilinear domains
- Parametrized complexity theory.
- What’s Next? Future Directions in Parameterized Complexity
- A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras
- Guarding terrains via local search
- On characterizing terrain visibility graphs
- Reflections on Multivariate Algorithmics and Problem Parameterization
- Terrain Guarding is NP-Hard
- The Lost Continent of Polynomial Time: Preprocessing and Kernelization
- A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
- A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
- Computational complexity of art gallery problems
- Some NP-hard polygon decomposition problems
- On the combinatorial and algebraic complexity of quantifier elimination
- Exact Algorithms for Terrain Guarding
- Irrational Guards are Sometimes Needed
- Parameterized Hardness of Art Gallery Problems
- Kernelization
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- An exact algorithm for minimizing vertex guards on art galleries
- Algorithms for polytope covering and approximation
- Orthogonal Terrain Guarding is NP-complete
- The art gallery problem is ∃ ℝ-complete
- Unsolved problems in visibility graphs of points, segments, and polygons
- A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
- Visibility Algorithms in the Plane
- Parameterized Algorithms
- Inapproximability results for guarding polygons and terrains
- The Parameterized Complexity of Guarding Almost Convex Polygons.
This page was built for publication: Parameterized Analysis of Art Gallery and Terrain Guarding
