scientific article; zbMATH DE number 7236415

DOI10.4230/LIPICS.SOCG.2018.11MaRDI QIDQ5115778zbMATH OpenFDO

Authors Édouard Bonnet, Panos Giannopoulos

Publication date 18 August 2020

Full work available at URL https://arxiv.org/abs/1710.00386

zbMATH Keywords

computational complexityrectilinear terrainterrain guarding

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Orthogonal terrain guarding is NP-complete
• Terrain guarding is NP-hard
• scientific article; zbMATH DE number 6297811
• Exact algorithms for terrain guarding
• Exact algorithms for terrain guarding
• Guarding thin orthogonal polygons is hard
• An Approximation Scheme for Terrain Guarding
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• A constant-factor approximation algorithm for optimal terrain guarding

Cites work

• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• An approximation algorithm for the art gallery problem
• Approximate guarding of monotone and rectilinear polygons
• Approximation algorithms for maximum independent set of pseudo-disks
• Exact algorithms for terrain guarding
• Finding small hitting sets in infinite range spaces of bounded VC-dimension
• Guarding galleries and terrains
• Guarding terrains via local search
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• Improved approximation algorithms for geometric set cover
• Improved approximation for guarding simple galleries from the perimeter
• Improved approximations for guarding 1.5-dimensional terrains
• Improved results on geometric hitting set problems
• Inapproximability results for guarding polygons and terrains
• Lower bounds based on the exponential time hypothesis
• On the complexity of k-SAT
• Parameterized hardness of art gallery problems
• Planar Formulae and Their Uses
• Terrain guarding is NP-hard
• Which problems have strongly exponential complexity?

Cited in

(9)

• Parameter analysis for guarding terrains
• Terrain guarding is NP-hard
• Exact algorithms for terrain guarding
• Exact algorithms for terrain guarding
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• Orthogonal terrain guarding is NP-complete
• scientific article; zbMATH DE number 6297811 (Why is no real title available?)
• On Guarding Rectilinear Domains
• One-sided terrain guarding and chordal graphs

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5115778)