Experimental study on approximation algorithms for guarding sets of line segments

DOI10.1007/978-3-642-17289-2_57MaRDI QIDQ3077409zbMATH OpenOpenAlexFDO

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 algorithmart gallery problemguarding set of segmentsset coververtex cover

Mathematics Subject Classification ID

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

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

• Guarding a set of line segments in the plane
• 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?)
• 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)