کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
414252 | 680861 | 2015 | 15 صفحه PDF | دانلود رایگان |
Given a set P of n points in the plane, Covering Points by Lines is the problem of finding a minimum-cardinality set LL of lines such that every point p∈Pp∈P is incident to some line ℓ∈Lℓ∈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)O(logn), namely the ratio achieved by the greedy algorithm for Set Cover.In this paper, we give a lower bound of Ω(logn)Ω(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.
Journal: Computational Geometry - Volume 48, Issue 9, October 2015, Pages 703–717