Experimental study on approximation algorithms for guarding sets of line segments

DOI10.1007/978-3-642-17289-2_57zbMATH Open1279.90142OpenAlexW1515344112MaRDI QIDQ3077409FDOQ3077409

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Reducibility among Combinatorial Problems
• Title not available (Why is that?)
• Title not available (Why is that?)
• Worst-case-optimal algorithms for guarding planar graphs and polyhedral surfaces
• Title not available (Why is that?)
• Guarding a set of line segments in the plane

Cited In (4)

• Geometric hitting set for segments of few orientations
• 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

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)