On gallery watchmen in grids

DOI10.1016/0020-0190(86)90050-5zbMath0609.68048OpenAlexW2082141764MaRDI QIDQ1087018

Simeon C. Ntafos

Publication date: 1986

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(86)90050-5

zbMATH Keywords

computational geometrypolygon decompositiongallery watchman problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (13)

Covering grids and orthogonal polygons with periscope guards ⋮ An approximation algorithm for maximum \(P_{3}\)-packing in subcubic graphs ⋮ Art gallery problem with rook and queen vision ⋮ Hiding people in polygons ⋮ Cooperative mobile guards in grids ⋮ On Some City Guarding Problems ⋮ Bamboo Garden Trimming Problem (Perpetual Maintenance of Machines with Different Attendance Urgency Factors) ⋮ Watchman routes for lines and line segments ⋮ Packing \([1, \Delta \)-factors in graphs of small degree] ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ Bamboo garden trimming problem: priority schedulings ⋮ Graphs with equal domination and covering numbers ⋮ The searchlight problem for road networks

Cites Work

• Unnamed Item
• Some simplified NP-complete graph problems
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• Traditional Galleries Require Fewer Watchmen
• Decomposing a Polygon into Simpler Components
• Computational complexity of art gallery problems
• Some NP-hard polygon decomposition problems
• An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs

This page was built for publication: On gallery watchmen in grids