On guarding the vertices of rectilinear domains

DOI10.1016/j.comgeo.2007.02.002zbMath1149.65015OpenAlexW1970504456MaRDI QIDQ2477198

Matthew J. Katz, Gabriel S. Roisman

Publication date: 13 March 2008

Published in: Computational Geometry (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.comgeo.2007.02.002

zbMATH Keywords

approximation algorithmsNP-hardnessgeometric optimizationguardingvisibility coveragepiercing problems

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (19)

Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ One-sided discrete terrain guarding and chordal graphs ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ Vertex-to-point conflict-free chromatic guarding is NP-hard ⋮ Vertex Guarding for Dynamic Orthogonal Art Galleries ⋮ Guarding orthogonal art galleries with sliding cameras ⋮ Optimally guarding 2-reflex orthogonal polyhedra by reflex edge guards ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ On \(r\)-guarding SCOTs -- a new family of orthogonal polygons ⋮ A scheme for computing minimum covers within simple regions ⋮ The parameterized complexity of guarding almost convex polygons ⋮ One-sided terrain guarding and chordal graphs ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS ⋮ Approximation algorithms for art gallery problems in polygons ⋮ The art gallery theorem for polyominoes ⋮ Parameter analysis for guarding terrains ⋮ How to guard orthogonal polygons: diagonal graphs and vertex covers ⋮ Approximability of guarding weak visibility polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Guarding polyhedral terrains
• On rigid circuit graphs
• Covering orthogonal polygons with star polygons: The perfect graph approach
• An optimal visibility graph algorithm for triangulated simple polygons
• A combinatorial theorem in plane geometry
• On the complexity of locating linear facilities in the plane
• Almost optimal set covers in finite VC-dimension
• A 4-Approximation Algorithm for Guarding 1.5-Dimensional Terrains
• Computational complexity of art gallery problems
• Some NP-hard polygon decomposition problems
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
• A randomized art-gallery algorithm for sensor placement
• Improved approximation algorithms for geometric set cover
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• Automata, Languages and Programming
• Inapproximability results for guarding polygons and terrains

This page was built for publication: On guarding the vertices of rectilinear domains