McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome.

DATE: Friday, October 22nd, 1999
TIME: 12:00-13:00
PLACE: McConnell 320
TITLE: Minimum Convex Partition of a Constrained Point Set
SPEAKER: Thomas Fevens, Deptartment of Computing and Information Science, Queen's University at Kingston.  

A minimum convex partition with respect to a point set S is a partition of the plane into cells such that each cell is a convex polygon, at each corner of a cell is a point from S, and the total number of convex polygons is minimized. In general, it appears that finding a minimum convex partition of a point set is computationally difficult. Thus a fruitful pursuit is to look at situations where efficient algorithms can be obtained.

In my talk, I will present an algorithm that determines a minimum convex partition of points that is efficient when the points lie on a fixed number of convex onion layers. If an onion peeling of the set of n points has h layers, then our algorithm runs in O(n^{3h+3}) time.

This is joint work with Henk Meijer and David Rappaport, both of Queen's University at Kingston.

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