Parameterized Hardness of Art Gallery Problems

DOI10.1145/3398684MaRDI QIDQ5888933zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

computational geometryparameterized complexityintractabilityart galleryETH lower bound

Mathematics Subject Classification ID

Computer science (68-XX)

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

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)