Guarding monotone art galleries with sliding cameras in linear time

DOI10.1016/J.JDA.2017.04.005MaRDI QIDQ2363353zbMATH OpenOpenAlexFDO

Authors Stephane Durocher, Saeed Mehrabi, Mark de Berg

Publication date 13 July 2017

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2017.04.005

zbMATH Keywords

dynamic programmingorthogonal polygonsart gallery problemsliding cameras

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Numerical aspects of computer graphics, image analysis, and computational geometry (65D18)

Recommendations

• Guarding monotone art galleries with sliding cameras in linear time
• Guarding orthogonal art galleries with sliding cameras
• Covering orthogonal polygons with sliding \(k\)-transmitters
• On guarding orthogonal polygons with sliding cameras

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• A combinatorial theorem in plane geometry
• Almost optimal set covers in finite VC-dimension
• Approximate guarding of monotone and rectilinear polygons
• Approximation algorithms for art gallery problems in polygons
• Combinatorics and complexity of guarding polygons with edge and point 2-transmitters
• Computational complexity of art gallery problems
• Coverage with \(k\)-transmitters in the presence of obstacles
• Fast vertex guarding for polygons with and without holes
• Guarding monotone art galleries with sliding cameras in linear time
• Guarding orthogonal art galleries using sliding cameras: algorithmic and hardness results
• Guarding orthogonal art galleries with sliding cameras
• Improved approximation for guarding simple galleries from the perimeter
• Introduction to algorithms.
• On guarding orthogonal polygons with sliding cameras
• POLYGON DECOMPOSITION AND THE ORTHOGONAL ART GALLERY PROBLEM
• Parameterized hardness of art gallery problems
• Terrain guarding is NP-hard
• The art gallery theorem for polyominoes
• Two NP‐Hard Art‐Gallery Problems for Ortho‐Polygons

Cited in

(4)

• Guarding monotone art galleries with sliding cameras in linear time
• Guarding orthogonal art galleries with sliding cameras
• Guarding orthogonal art galleries with sliding k-transmitters: hardness and approximation
• Guarding orthogonal art galleries with sliding cameras

This page was built for publication: Guarding monotone art galleries with sliding cameras in linear time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2363353)