Parameterized Hardness of Art Gallery Problems

DOI10.1145/3398684OpenAlexW2546555264MaRDI QIDQ5888933FDOQ5888933

Authors: Édouard Bonnet, Tillmann Miltzow 

Publication date: 26 April 2023

Published in: ACM Transactions on Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3398684

Recommendations

• Parameterized hardness of art gallery problems
• The parameterized complexity of guarding almost convex polygons
• The Parameterized Complexity of Guarding Almost Convex Polygons.
• Computational complexity of art gallery problems
• Vertex guarding in weak visibility polygons

zbMATH Keywords

computational geometryparameterized complexityintractabilityart galleryETH lower bound

Mathematics Subject Classification ID

Computer science (68-XX)

Cited In (7)

• A practical algorithm with performance guarantees for the art gallery problem
• Parameter analysis for guarding terrains
• Observation routes and external watchman routes
• Observation routes and external watchman routes
• The parameterized complexity of guarding almost convex polygons
• Topological art in simple galleries
• The Parameterized Complexity of Guarding Almost Convex Polygons.

This page was built for publication: Parameterized Hardness of Art Gallery Problems

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