Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

From MaRDI portal
Publication:4835529

DOI10.1002/malq.19950410212zbMath0827.68115OpenAlexW2115708125MaRDI QIDQ4835529

Dietmar Schuchardt, Hans-Dietrich Hecker

Publication date: 17 December 1995

Published in: Mathematical Logic Quarterly (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/malq.19950410212




Related Items (30)

Guarding monotone art galleries with sliding cameras in linear timeParameterized Analysis of Art Gallery and Terrain GuardingOn boundaries of highly visible spaces and applicationsVertex-to-point conflict-free chromatic guarding is NP-hardVertex Guarding for Dynamic Orthogonal Art GalleriesGuarding orthogonal art galleries with sliding camerasOn orthogonally guarding orthogonal polygons with bounded treewidthOptimally guarding 2-reflex orthogonal polyhedra by reflex edge guardsComputational Complexity of the $$r$$-visibility Guard Set Problem for PolyominoesA 3-Approximation Algorithm for Guarding Orthogonal Art Galleries with Sliding CamerasThe dispersive art gallery problemConstrained Light Deployment for Reducing Energy Consumption in BuildingsOn \(r\)-guarding SCOTs -- a new family of orthogonal polygonsCombinatorics and complexity of guarding polygons with edge and point 2-transmittersThe parameterized complexity of guarding almost convex polygonsTopological art in simple galleriesFinding minimum witness sets in orthogonal polygonsClearing an orthogonal polygon to find the evadersOn Guarding Orthogonal Polygons with Sliding CamerasMobile versus point guardsGUARDING ORTHOGONAL ART GALLERIES WITH SLIDING CAMERASAn exact algorithm for minimizing vertex guards on art galleriesOn guarding the vertices of rectilinear domainsGuarding orthogonal art galleries with sliding \(k\)-transmitters: hardness and approximationApproximation algorithms for art gallery problems in polygonsThe art gallery theorem for polyominoesCovering orthogonal polygons with sliding \(k\)-transmittersPolygon exploration with time-discrete visionHow to guard orthogonal polygons: diagonal graphs and vertex coversApproximability of guarding weak visibility polygons



Cites Work


This page was built for publication: Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons