On the approximability of covering points by lines and related problems

Adrian Dumitrescu, Minghui Jiang

Given a set $P$ of $n$ points in the plane, {\sc Covering Points by Lines} is the problem of finding a minimum-cardinality set $Ł$ of lines such that every point $p\in P$ is incid…