Guarding thin orthogonal polygons is hard

DOI10.1007/978-3-642-40164-0_29MaRDI QIDQ2842794zbMATH OpenOpenAlexFDO

Authors Ana Paula Tomás

Publication date 16 August 2013

Published in Fundamentals of Computation Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-40164-0_29

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• On r-guarding thin orthogonal polygons
• Characterizing and Covering Some Subclasses of Orthogonal Polygons
• scientific article; zbMATH DE number 975343
• On Guarding Rectilinear Domains
• GUARDING RECTANGULAR PARTITIONS

Cited in

(16)

• Further NP-hard problems for minimal polygon coverings
• Guarding orthogonal art galleries with sliding k-transmitters: hardness and approximation
• Guarding disjoint triangles and claws in the plane
• Tight bounds for illuminating and covering of orthotrees with vertex lights and vertex beacons
• On orthogonally guarding orthogonal polygons with bounded treewidth
• On guarding orthogonal polygons with sliding cameras
• Polygon guarding with orientation
• Characterizing and Covering Some Subclasses of Orthogonal Polygons
• GUARDING A POLYGON FROM TWO NEARLY-OPPOSITE DIRECTIONS
• On r-guarding thin orthogonal polygons
• scientific article; zbMATH DE number 7236415 (Why is no real title available?)
• THE MINIMUM GUARDING TREE PROBLEM
• On \(r\)-guarding SCOTs -- a new family of orthogonal polygons
• Guarding polyominoes under \(k\)-hop visibility
• Ortho-unit polygons can be guarded with at most \(\left\lfloor \frac{n-4}{8} \right\rfloor\) guards
• Guarding polyominoes under k-hop visibility

This page was built for publication: Guarding thin orthogonal polygons is hard

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2842794)