Guarding Lines and 2-Link Polygons is APX-hard
Björn Brodén, Mikael Hammar, Bengt J. Nilsson · Malmö University Publications (Malmö University) · 2001
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