On the approximability of covering points by lines and related problems

Given a set P of n points in the plane, COVERING POINTS BY LINES is the problem of finding a minimum-cardinality set L of lines such that every point p is an element of P is incident to some line l is an element of L. As a geometric variant of SET COVER, COVERING POINTS BY LINES IS still NP-hard. Moreover, it has been proved to be APX-hard, and hence does not admit any polynomial-time approximation scheme unless P = NP. In contrast to the small constant approximation lower bound implied by APX-hardness, the current best approximation ratio for COVERING POINTS BY LINES is still O(logn), namely the ratio achieved by the greedy algorithm for SET COVER. In this paper, we give a lower bound of Omega(logn) on the approximation ratio of the greedy algorithm for COVERING POINTS BY LINES. We also study several related problems including MAXIMUM POINT COVERAGE BY LINES, MINIMUM-LINK COVERING TOUR, MINIMUM-LINK SPANNING TOUR, and MIN-MAX-TURN HAMILTONIAN TOUR. We show that all these problems are either APX-hard or at least NP-hard. In particular, our proof of APX-hardness of MIN-MAX-TURN HAMILTONIAN TOUR sheds light on the difficulty Of BOUNDED-TURN-MINIMUM-LENGTH HAMILTONIAN TOUR, a problem proposed by Aggarwal et al. at SODA 1997. (C) 2015 Elsevier B.V. All rights reserved.