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.