McGill University - School of Computer Science

Doctoral Oral

All are welcome.
DATE: Tuesday, October 14th, 1997
TIME: 14h00
PLACE: McConnell 320
TITLE: "On the complexity of vertex and facet enumeration for convex polytopes"
SPEAKER: David Bremner
COMMITTEE:





Prof. Therien (Chairman)
Prof. Avis (Supervisor)
Prof. Panangaden
Prof. Whitesides
Prof. Goffin (External Member, Management)
Pro Dean (TBA)
Every convex polytope is both the intersection of a finite set of halfspaces and the convex hull of a finite vertex set. Transforming from the halfspaces (vertices, respectively) to the vertices (halfspaces, respectively) is called vertex enumeration (facet enumeration, respectively). It is an open problem whether there is an algorithm for these two problems polynomial in the input and the output size. For each of the known methods, this thesis develops a characterization of what constitutes an easy or difficult input. Example families of polytopes are presented that show that none of the known methods will yield a polynomial algorithm. Ona the other hand, a family of polytopes difficult for one class of algorithms can (sometimes) be easily solvable for another class of algorithms; the characterizations given here can be used to guide a choice of algorithms. Similarly, although the general problems of vertex and facet enumeration are equivalent by the duality of convex polytopes, for fixed polytope family and algorithm, one of these directions can be much easier than the other. This thesis presents a new class of algorithms that use the easy direction as an oracle to solve the seemingly difficult direction.
This information is available at http://cgm.cs.mcgill.ca/~therese/seminar.
Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to Therese Biedl at therese@cgm.cs.mcgill.ca.