Guarding a set of line segments in the plane

DOI10.1016/J.TCS.2010.08.014zbMATH Open1207.68414OpenAlexW2084452856MaRDI QIDQ630591FDOQ630591

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)