Experimental study on approximation algorithms for guarding sets of line segments

DOI10.1007/978-3-642-17289-2_57MaRDI QIDQ3077409zbMATHOpenAlexFDO

Authors Valentin E. Brimkov, Michael Mastroianni, Andrew Leach, Jimmy Wu

Publication date 22 February 2011

Published in Advances in Visual Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-17289-2_57

zbMATH Keywords

approximation algorithmset coververtex coverart gallery problemguarding set of segments

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Extremal problems in graph theory (05C35) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Graph representations (geometric and intersection representations, etc.) (05C62)

Recommendations

• Guarding a set of line segments in the plane
• Approximability issues of guarding a set of segments
• Approximation algorithms for a geometric set cover problem
• Guarding galleries and terrains
• Approximate guarding of monotone and rectilinear polygons

Cites work

• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 3793772 (Why is no real title available?)
• scientific article; zbMATH DE number 1391661 (Why is no real title available?)
• scientific article; zbMATH DE number 3102025 (Why is no real title available?)
• Guarding a set of line segments in the plane
• Reducibility among combinatorial problems
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

Cited in

(3)

• Approximability issues of guarding a set of segments
• Approximation algorithms for a geometric set cover problem
• Guarding a set of line segments in the plane

This page was built for publication: Experimental study on approximation algorithms for guarding sets of line segments

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