On the approximability of covering points by lines and related problems (Q904111)

The authors study the computational complexity of several different problems. The first studied problem is the covering points by lines problem, i.e., given a set \(P\) of \(n\) points in the plane find a minimum-cardinality set \(L\) of lines such that every point \(p \in P\) is in some line \(l \in L\). They prove that the approximation ratio of the greedy algorithm for solving this problem is \(\Omega(\log n)\) and that the problem is APX-hard. Next, they study the maximum point coverage by lines problem, i.e., given a set \(P\) of \(n\) points in the plane and a number \(k\) find \(k\) lines that cover the maximum number of points in \(P\). Also, in this case, they prove that the problem is APX-hard. Then, they prove that the minimum-link covering tour problem is APX-hard and that the minimum-link spanning tour is NP-hard. The minimum-link covering tour (minimum-link spanning tour) problem is a problem in which for a given set \(P\) of \(n\) points in the plane we look for the covering tour (spanning tour) with the minimum number of link (segments). Finally, the authors study the min-max-turn Hamiltonian tour problem and the bounded-turn-minimum-length Hamiltonian tour problem. In the first problem for a given \(n\) points in the plane we search for a Hamiltonian tour that minimizes the maximum turning angle, whereas in the second problem for given \(n\) points in the plane and an angle \(\alpha \in [0, \pi]\), we search for a Hamiltonian tour with each turning angle at most \(\alpha\), if it exists, that has the minimum length. They prove that the min-max-turn Hamiltonian tour problem is APX-hard and the bounded-turn-minimum-length Hamiltonian tour problem is NP-hard.