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.