Tight bounds for conflict-free chromatic guarding of orthogonal art galleries

DOI10.1016/j.comgeo.2018.01.003zbMath1443.68201OpenAlexW2782773468MaRDI QIDQ1615774

Frank Hoffmann, Subhash Suri, Max Willert, Klaus Kriegel, Kevin Verbeek

Publication date: 31 October 2018

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

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/5097/

zbMATH Keywords

art gallery problemhypergraph coloringorthogonal polygons

Mathematics Subject Classification ID

Hypergraphs (05C65) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Vertex-to-point conflict-free chromatic guarding is NP-hard, The dispersive art gallery problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lower bounds for weak epsilon-nets and stair-convexity
• Covering orthogonal polygons with star polygons: The perfect graph approach
• Coloring axis-parallel rectangles
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• A data structure for dynamic trees
• Conflict-free chromatic art gallery coverage
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Improved bounds for the conflict-free chromatic art gallery problem