Algorithms Seminar

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.