Maximizing the guarded boundary of an Art Gallery is APX-complete

DOI10.1016/J.COMGEO.2006.12.001MaRDI QIDQ2385696zbMATH OpenOpenAlexFDO

Authors Christodoulos Fragoudakis, Euripides Markou, Stathis Zachos

Publication date 12 October 2007

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2006.12.001

zbMATH Keywords

approximation algorithmsart gallerynumerical examplesvisibility

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2011842
• Inapproximability results for guarding polygons and terrains
• Approximation algorithms for art gallery problems in polygons
• Approximability of guarding weak visibility polygons
• Guarding Art Galleries: The Extra Cost for Sculptures Is Linear

Cites work

• Approximation algorithms for NP-hard problems.
• Automata, Languages and Programming
• Computational complexity of art gallery problems
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 6469255 (Why is no real title available?)
• Optimum placement of guards

Cited in

(6)

• Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
• Improved Bounds for Wireless Localization
• scientific article; zbMATH DE number 2011842 (Why is no real title available?)
• scientific article; zbMATH DE number 219237 (Why is no real title available?)
• Stathis Zachos at 70!
• Improved bounds for wireless localization

This page was built for publication: Maximizing the guarded boundary of an Art Gallery is APX-complete

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