Malmö University Publications (Malmö University) · 2001 · 41 citations · 0 references
Open access
Natural SciencesComputer ScienceMathematicsCombinatoricsDiscrete MathematicsGeometryGeometric OptimizationCovering Problems
We prove that the minimum line covering problem and the minimum guard covering problem restricted to 2- link polygons are APX-hard. keywords: Computational Geometry, Polygon Decomposition, Art Gallery Theorem, Minimum Guard Covering, Minimum Line Covering. 1