| DATE: | Wednesday, October 24th |
| TIME: | 4:30 PM - 5:30 PM |
| PLACE: | McConnell 320 |
| 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.