McGill University - School of Computer Science

Algorithms Seminar Fall 2001

Everybody is welcome!

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.