Guarding a set of line segments in the plane

DOI10.1016/J.TCS.2010.08.014MaRDI QIDQ630591zbMATH OpenOpenAlexFDO

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

Publication date 17 March 2011

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2010.08.014

zbMATH Keywords

set coververtex coverpolynomial algorithmart-gallery problemguarding set of segmentsstrongly NP-complete problem

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Experimental study on approximation algorithms for guarding sets of line segments
• Approximability issues of guarding a set of segments
• THE MINIMUM GUARDING TREE PROBLEM
• An art gallery theorem for line segments in the plane
• scientific article; zbMATH DE number 4062605

Cites work

• scientific article; zbMATH DE number 3919830 (Why is no real title available?)
• scientific article; zbMATH DE number 4065813 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (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 1820633 (Why is no real title available?)
• scientific article; zbMATH DE number 1424310 (Why is no real title available?)
• scientific article; zbMATH DE number 3102025 (Why is no real title available?)
• A combinatorial theorem in plane geometry
• A short proof of Chvatal's Watchman Theorem
• Algorithms for Reporting and Counting Geometric Intersections
• Digitization scheme that assures faithful reconstruction of plane figures
• Introduction to algorithms
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces

Cited in

(12)

• Guarding disjoint triangles and claws in the plane
• The searchlight problem for road networks
• THE MINIMUM GUARDING TREE PROBLEM
• Watchman routes for lines and line segments
• Complexity of minimum corridor guarding problems
• Approximability issues of guarding a set of segments
• Experimental study on approximation algorithms for guarding sets of line segments
• Approximation algorithms for a geometric set cover problem
• scientific article; zbMATH DE number 4060719 (Why is no real title available?)
• Intersections and circuits in sets of line segments
• GUARDING RECTANGULAR PARTITIONS
• Computational complexity for the problem of optimal intersection of straight line segments by disks

This page was built for publication: Guarding a set of line segments in the plane

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