Computational complexity of art gallery problems

DOI10.1109/TIT.1986.1057165zbMath0593.68035WikidataQ56504470 ScholiaQ56504470MaRDI QIDQ3723700

No author found.

Publication date: 1986

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

NP-hard computational geometry star-shaped polygons minimum number of edge guards minimum number of point guards minimum number of vertex guards n-wall simply connected art gallery simply connected polygonal region simply polygon

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Polyhedra and polytopes; regular figures, division of spaces (51M20)

Related Items (82)

Optimum placement of guards ⋮ Guarding monotone art galleries with sliding cameras in linear time ⋮ Covering grids and orthogonal polygons with periscope guards ⋮ Parameterized Analysis of Art Gallery and Terrain Guarding ⋮ Minimal link visibility paths inside a simple polygon ⋮ An optimal algorithm to solve the minimum weakly cooperative guards problem for 1-spiral polygons ⋮ On gallery watchmen in grids ⋮ On boundaries of highly visible spaces and applications ⋮ The prison yard problem ⋮ The VC-dimension of visibility on the boundary of monotone polygons ⋮ Approximate guarding of monotone and rectilinear polygons ⋮ Multi-agent deployment for visibility coverage in polygonal environments with holes ⋮ Computing a shortest watchman path in a simple polygon in polynomial-time ⋮ Line segment visibility with sidedness constraints ⋮ SEARCHING POLYHEDRA BY ROTATING HALF-PLANES ⋮ Hiding points in arrangements of segments ⋮ Maximizing the guarded boundary of an Art Gallery is APX-complete ⋮ Vertex-to-point conflict-free chromatic guarding is NP-hard ⋮ A tight bound for point guards in piecewise convex art galleries ⋮ Algorithms for art gallery illumination ⋮ Art gallery problem with rook and queen vision ⋮ Guarding orthogonal art galleries with sliding cameras ⋮ On orthogonally guarding orthogonal polygons with bounded treewidth ⋮ Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons ⋮ Hiding people in polygons ⋮ Computational Complexity of the $$r$$-visibility Guard Set Problem for Polyominoes ⋮ A 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding Cameras ⋮ Guarding a Polygon Without Losing Touch ⋮ Connecting guards with minimum Steiner points inside simple polygons ⋮ Minimizing visible edges in polyhedra ⋮ Reflective guarding a gallery ⋮ The dispersive art gallery problem ⋮ On $r$-guarding SCOTs -- a new family of orthogonal polygons ⋮ On vertex guarding staircase polygons ⋮ On the complexity of half-guarding monotone polygons ⋮ On Some City Guarding Problems ⋮ Guarding Art Galleries: The Extra Cost for Sculptures Is Linear ⋮ Improved Bounds for Wireless Localization ⋮ Coverage with $k$-transmitters in the presence of obstacles ⋮ On colourability of polygon visibility graphs ⋮ Two-guarding a rectilinear polygon ⋮ Combinatorics and complexity of guarding polygons with edge and point 2-transmitters ⋮ The parameterized complexity of guarding almost convex polygons ⋮ Topological art in simple galleries ⋮ Improved approximation for guarding simple galleries from the perimeter ⋮ ENERGY-AWARE STAGE ILLUMINATION ⋮ Finding minimum witness sets in orthogonal polygons ⋮ Clearing an orthogonal polygon to find the evaders ⋮ Algorithm 966 ⋮ On Guarding Orthogonal Polygons with Sliding Cameras ⋮ Multiple point visibility and related problems ⋮ Guarding curvilinear art galleries with vertex or point guards ⋮ Computing the maximum clique in the visibility graph of a simple polygon ⋮ GENERALIZED WATCHMAN ROUTE PROBLEM WITH DISCRETE VIEW COST ⋮ On covering orthogonal polygons with star-shaped polygons ⋮ An exact algorithm for minimizing vertex guards on art galleries ⋮ On guarding the vertices of rectilinear domains ⋮ Guarding orthogonal art galleries with sliding $k$-transmitters: hardness and approximation ⋮ Approximation algorithms for art gallery problems in polygons ⋮ Improved bounds for wireless localization ⋮ Volumetric untrimming: precise decomposition of trimmed trivariates into tensor products ⋮ Finding minimum hidden guard sets in polygons --- tight approximability results ⋮ Towards Optimal Positioning of Surveillance UGVs ⋮ Guarding curvilinear art galleries with edge or mobile guards via 2-dominance of triangulation graphs ⋮ The art gallery theorem for polyominoes ⋮ LOCATING GUARDS FOR VISIBILITY COVERAGE OF POLYGONS ⋮ Illumination in the presence of opaque line segments in the plane ⋮ Clique-width of point configurations ⋮ On Colourability of Polygon Visibility Graphs ⋮ Facets for art gallery problems ⋮ Optimal art gallery localization is NP-hard ⋮ Isomorphism of spiral polygons ⋮ Covering orthogonal polygons with sliding $k$-transmitters ⋮ Multiple-guard kernels of simple polygons ⋮ Watchman routes in the presence of a pair of convex polygons ⋮ An $O(\lg \lg {\mathrm {OPT}})$-approximation algorithm for multi-guarding galleries ⋮ How to Keep an Eye on Small Things ⋮ On the number of guard edges of a polygon ⋮ Approximation algorithms for terrain guarding. ⋮ EDGE GUARDS IN STRAIGHT WALKABLE POLYGONS ⋮ A constant-factor approximation algorithm for vertex guarding a WV-polygon ⋮ Approximability of guarding weak visibility polygons

This page was built for publication: Computational complexity of art gallery problems