Guarding Lines and 2-Link Polygons is APX-hard

Björn Brodén, Mikael Hammar, Bengt J. Nilsson

Malmö University Publications (Malmö University) · 2001 · 41 citations · 0 references

Full text

Open access

Concepts

Abstract

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