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

DOI10.1016/J.COMGEO.2006.12.001zbMATH Open1124.65023OpenAlexW2099932624MaRDI QIDQ2385696FDOQ2385696

Stathis Zachos, Christodoulos Fragoudakis, Euripides Markou

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

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

zbMATH Keywords

numerical examplesapproximation algorithmsvisibilityart gallery

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Automata, Languages and Programming
• Title not available (Why is that?)
• Computational complexity of art gallery problems
• Optimum placement of guards

Cited In (6)

• Improved bounds for wireless localization
• Guarding Art Galleries: The Extra Cost for Sculptures Is Linear
• Title not available (Why is that?)
• Stathis Zachos at 70!
• Title not available (Why is that?)
• 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)