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.

Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at Algorithms Seminar organization.