Art gallery problem with rook and queen vision
DOI10.1007/s00373-020-02272-8zbMath1499.68359arXiv1810.10961OpenAlexW3124254980MaRDI QIDQ2657110
Publication date: 17 March 2021
Published in: Graphs and Combinatorics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1810.10961
computational geometryNP-hardnesschessboard complexpolyominoart gallery theoremguard numbervisibility coveragedomination problemN-queens problem
Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Combinatorial aspects of packing and covering (05B40) Polyominoes (05B50)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Guarding polyominoes, polycubes and polyhypercubes
- The art gallery theorem for polyominoes
- Partition into cliques for cubic graphs: Planar case, complexity and approximation
- A survey of known results and research areas for \(n\)-queens
- Representing a planar graph by vertical lines joining different levels
- A unified approach to visibility representations of planar graphs
- On gallery watchmen in grids
- Chessboard domination problems
- On the queen domination problem
- Polyominos and perfect graphs
- A combinatorial theorem in plane geometry
- A generalization of \textsc{Arc-Kayles}
- Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings
- Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
- Computational complexity of art gallery problems
- Chessboard Complexes and Matching Complexes
- The art gallery problem is ∃ ℝ-complete
- Complexity of n-Queens Completion
This page was built for publication: Art gallery problem with rook and queen vision
