Guarding a set of line segments in the plane

DOI10.1016/j.tcs.2010.08.014zbMath1207.68414OpenAlexW2084452856MaRDI QIDQ630591

Michael Mastroianni, Valentin E. Brimkov, Andrew J. Leach, Jimmy Ming-Tai 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

polynomial algorithmvertex coverset coverart-gallery problemguarding set of segmentsstrongly NP-complete problem

Mathematics Subject Classification ID

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

Related Items (8)

Approximation algorithms for a geometric set cover problem ⋮ Watchman routes for lines and line segments ⋮ Geometric hitting set for segments of few orientations ⋮ THE MINIMUM GUARDING TREE PROBLEM ⋮ Experimental Study on Approximation Algorithms for Guarding Sets of Line Segments ⋮ Intersections and circuits in sets of line segments ⋮ Approximability issues of guarding a set of segments ⋮ The searchlight problem for road networks

Cites Work

• Digitization scheme that assures faithful reconstruction of plane figures
• A short proof of Chvatal's Watchman Theorem
• A combinatorial theorem in plane geometry
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• Algorithms for Reporting and Counting Geometric Intersections
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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