Covering points with lines
Stefan Langerman, Pat Morin · 2001
Given a set of n points in the plane, is it possible to nd k lines that cover all the points in the set? We show that although this problem is NPhard, it can be solved eciently for small values of k. In particular, we give a O(nk log k + k ) algorithm for this problem, and a generalization to higher dimensions.