McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome!

DATE: Thursday, December 7th
TIME: 10:00 AM - 11:00 AM
PLACE: McConnell 320
TITLE: Vertex and Facet Enumeration for Convex Polytopes - Algorithms, Implementations and Applications
SPEAKER: Komei Fukuda,ETH Zentrum and EPF Lausanne

The vertex enumeration problem is to generate all vertices of a convex polytope in Rd given as the solution set to a system of linear inequalities. This problem in dual form is known as the convex hull computation or the facet enumeration problem for a given set of points in Rd. In this talk, we present old and new approaches to the problem, and in particular, key ideas behind recent algorithms that are polynomial for certain classes of polytopes. Here an algorithm is called polynomial if it runs in time polynomial in the sizes of input and output. No polynomial algorithm is known for the general case. Some computational results are presented to illustrate how important the theoretical efficiency is for solving large- scale problems. New applications of the general dimensional convex hull and the vertex enumeration indicate the diversity of applicable areas.

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