Computational complexity of art gallery problems
From MaRDI portal
Recommendations
Cited in
(97)- On colourability of polygon visibility graphs
- Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons
- Clearing an orthogonal polygon to find the evaders
- An exact algorithm for minimizing vertex guards on art galleries
- Volumetric untrimming: precise decomposition of trimmed trivariates into tensor products
- On guarding orthogonal polygons with sliding cameras
- Improved approximation for guarding simple galleries from the perimeter
- Hiding people in polygons
- Guarding polyominoes under k-hop visibility
- The art gallery problem is \(\exists \mathbb{R}\)-complete
- Improved bounds for wireless localization
- POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
- Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
- A constant-factor approximation algorithm for vertex guarding a WV-polygon
- Multi-agent deployment for visibility coverage in polygonal environments with holes
- Watchman routes in the presence of a pair of convex polygons
- On the complexity of half-guarding monotone polygons
- scientific article; zbMATH DE number 4062605 (Why is no real title available?)
- Approximation algorithms for art gallery problems in polygons
- Reflective guarding a gallery
- Guarding curvilinear art galleries with vertex or point guards
- On gallery watchmen in grids
- Approximability of guarding weak visibility polygons
- The VC-dimension of visibility on the boundary of monotone polygons
- A practical algorithm with performance guarantees for the art gallery problem
- Guarding orthogonal art galleries with sliding k-transmitters: hardness and approximation
- scientific article; zbMATH DE number 4117851 (Why is no real title available?)
- Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs
- Art gallery problem with rook and queen vision
- Computational complexity of the r-visibility guard set problem for polyominoes
- scientific article; zbMATH DE number 4062591 (Why is no real title available?)
- Minimal link visibility paths inside a simple polygon
- On \(r\)-guarding SCOTs -- a new family of orthogonal polygons
- Parameterized hardness of art gallery problems
- Approximation algorithms for terrain guarding.
- A practical algorithm with performance guarantees for the art gallery problem
- Line segment visibility with sidedness constraints
- Visibility extension via reflection
- scientific article; zbMATH DE number 6729378 (Why is no real title available?)
- Finding minimum hidden guard sets in polygons --- tight approximability results
- Computing a shortest watchman path in a simple polygon in polynomial-time
- On Some City Guarding Problems
- Towards optimal positioning of surveillance UGVs
- On boundaries of highly visible spaces and applications
- Illumination in the presence of opaque line segments in the plane
- How to Keep an Eye on Small Things
- An \(O(\lg \lg {\mathrm {OPT}})\)-approximation algorithm for multi-guarding galleries
- Maximizing the guarded boundary of an Art Gallery is APX-complete
- Guarding monotone art galleries with sliding cameras in linear time
- On the number of guard edges of a polygon
- Guarding orthogonal art galleries with sliding cameras
- Approximate guarding of monotone and rectilinear polygons
- Complexity of minimum corridor guarding problems
- EDGE GUARDS IN STRAIGHT WALKABLE POLYGONS
- On colourability of polygon visibility graphs
- Two-guarding a rectilinear polygon
- Facets for art gallery problems
- Computing the maximum clique in the visibility graph of a simple polygon
- Vertex-to-point conflict-free chromatic guarding is NP-hard
- An optimal algorithm to solve the minimum weakly cooperative guards problem for 1-spiral polygons
- The parameterized complexity of guarding almost convex polygons
- On orthogonally guarding orthogonal polygons with bounded treewidth
- On guarding the vertices of rectilinear domains
- Optimum placement of guards
- The art gallery theorem for polyominoes
- Searching polyhedra by rotating half-planes
- Guarding a Polygon Without Losing Touch
- scientific article; zbMATH DE number 4128383 (Why is no real title available?)
- Clique-width of point configurations
- Topological art in simple galleries
- Parameterized Hardness of Art Gallery Problems
- A tight bound for point guards in piecewise convex art galleries
- Algorithms for art gallery illumination
- Improved Bounds for Wireless Localization
- Locating guards for visibility coverage of polygons
- The prison yard problem
- The dispersive art gallery problem
- Parameterized Analysis of Art Gallery and Terrain Guarding
- Hiding points in arrangements of segments
- Robustly guarding polygons
- Covering grids and orthogonal polygons with periscope guards
- ENERGY-AWARE STAGE ILLUMINATION
- GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST
- Isomorphism of spiral polygons
- Multiple-guard kernels of simple polygons
- Optimal art gallery localization is NP-hard
- Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
- Minimizing visible edges in polyhedra
- Covering orthogonal polygons with sliding \(k\)-transmitters
- Coverage with k-transmitters in the presence of obstacles
- Connecting guards with minimum Steiner points inside simple polygons
- Finding minimum witness sets in orthogonal polygons
- Multiple point visibility and related problems
- On covering orthogonal polygons with star-shaped polygons
- Guarding polyominoes under \(k\)-hop visibility
- Algorithm 966: A practical iterative algorithm for the art gallery problem using integer linear programming
- On vertex guarding staircase polygons
This page was built for publication: Computational complexity of art gallery problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3723700)
