On Guarding Line Arrangements
We study the problem of guarding a set of straight lines in the plane by selecting a minimum-cardinality set of points such that every line contains at least one selected point. This problem is known to be strongly NP-hard \cite{megiddo}. We investigate approximation algorithms for the problem and analyze their performance guarantees under various structural assumptions on the underlying line arrangement. In particular, we present approximation schemes based on set-cover techniques, relaxation methods, and properties of maximal lines. We establish constant-factor bounds on the approximation…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2611.02046
curl -X POST /api/v1/records/arxiv/2611.02046/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.02046/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'