|DATE:||Wednesday, October 24th|
|TIME:||4:30 PM - 5:30 PM|
|TITLE:||Covering Points with Lines|
|SPEAKER:||Stefan Langerman, School of Computer Science, McGill University|
Given a set of n points in the plane, is it possible to find k lines that cover all the points in the set? We show that although this problem is NP-hard, it can be solved efficiently for small values of k. In particular, we give a O(n k log k + k^(2k+2)) algorithm for this problem, and a generalization to higher dimensions.
This is joint work with Pat Morin.