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

art gallerycomputational geometryETH lower boundintractabilityparameterized complexity

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

(13)

• Parameter analysis for guarding terrains
• The Art Gallery Problem is ∃ℝ-complete
• The Parameterized Complexity of Guarding Almost Convex Polygons.
• Observation routes and external watchman routes
• The parameterized complexity of guarding almost convex polygons
• Topological art in simple galleries
• A practical algorithm with performance guarantees for the art gallery problem
• Observation routes and external watchman routes
• Robustly guarding polygons
• Twin-width. VIII: Delineation and win-wins
• A practical algorithm with performance guarantees for the art gallery problem
• Can you link up with treewidth?
• Can you link up with treewidth?

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)