Robustly guarding polygons

DOI10.4230/LIPICS.SOCG.2024.47MaRDI QIDQ6895854zbMATH OpenFDO

Authors Rathish Das, Omrit Filtser, Matthew J. Katz, Joseph S. B. Mitchell

Publication date 24 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.SOCG.2024.47

zbMATH Keywords

approximation algorithmsgeometric optimizationguarding

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25)

Cites work

• A constant-factor approximation algorithm for vertex guarding a WV-polygon
• A Constant‐Factor Approximation Algorithm for Optimal 1.5D Terrain Guarding
• A Pseudopolynomial Time O(logn)-Approximation Algorithm for Art Gallery Problems
• Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
• Almost optimal set covers in finite VC-dimension
• An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
• An approximation algorithm for the art gallery problem
• Approximability of guarding weak visibility polygons
• Approximate guarding of monotone and rectilinear polygons
• Approximation Schemes for Covering and Packing
• Computational complexity of art gallery problems
• Efficient guarding of polygons and terrains
• Guarding galleries and terrains
• Guarding galleries where every point sees a large area
• Guarding galleries where no point sees a small area.
• Guarding terrains via local search
• scientific article; zbMATH DE number 6776481 (Why is no real title available?)
• Improved approximation for guarding simple galleries from the perimeter
• Inapproximability results for guarding polygons and terrains
• Irrational guards are sometimes needed
• Locating guards for visibility coverage of polygons
• On galleries with no bad points
• Parameterized Analysis of Art Gallery and Terrain Guarding
• Parameterized Hardness of Art Gallery Problems
• Smoothing the Gap Between NP and ER
• Terrain-like graphs: PTASs for guarding weakly-visible polygons and terrains
• The Art Gallery Problem is ∃ℝ-complete
• The Complexity of the Union of $(\alpha,\beta)$-Covered Objects
• The continuous 1.5D terrain guarding problem: discretization, optimal solutions, and PTAS
• The Parameterized Complexity of Guarding Almost Convex Polygons.
• Triangulating and guarding realistic polygons

This page was built for publication: Robustly guarding polygons

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