POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM

DOI10.1142/S0218195907002264zbMath1144.65015OpenAlexW2168192372MaRDI QIDQ3442762

J. Mark Keil, Chris Worman

Publication date: 23 May 2007

Published in: International Journal of Computational Geometry & Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0218195907002264

zbMATH Keywords

polynomial-time algorithmpolygon decompositionart galleryorthogonal polygonspolygon covering

Mathematics Subject Classification ID

Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Related Items (24)

Tight bounds for conflict-free chromatic guarding of orthogonal art galleries ⋮ Guarding monotone art galleries with sliding cameras in linear time ⋮ Universal Guard Problems ⋮ Note on covering monotone orthogonal polygons with star-shaped polygons ⋮ A Scheme for Computing Minimum Covers within Simple Regions ⋮ Art gallery problem with rook and queen vision ⋮ Guarding orthogonal art galleries with sliding cameras ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ Minimum r-Star Cover of Class-3 Orthogonal Polygons ⋮ The dispersive art gallery problem ⋮ On \(r\)-guarding SCOTs -- a new family of orthogonal polygons ⋮ A scheme for computing minimum covers within simple regions ⋮ Finding minimum witness sets in orthogonal polygons ⋮ Clearing an orthogonal polygon to find the evaders ⋮ Mobile versus point guards ⋮ GUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERAS ⋮ LINEAR-TIME 3-APPROXIMATION ALGORITHM FOR THE r-STAR COVERING PROBLEM ⋮ The art gallery theorem for polyominoes ⋮ LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS ⋮ Linear-Time 3-Approximation Algorithm for the r-Star Covering Problem ⋮ Covering orthogonal polygons with sliding \(k\)-transmitters ⋮ Altitude terrain guarding and guarding uni-monotone polygons

Cites Work

• Unnamed Item
• Unnamed Item
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Star-cutsets and perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Decomposing a Polygon into Simpler Components
• Graph Classes: A Survey

This page was built for publication: POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM