McGill University - School of Computer Science

Algorithms Seminar

Everybody is welcome!
DATE: Wednesday, September 6th
TIME: 12:00 PM - 1:00 PM
PLACE: McConnell 320
TITLE: Extended Convex Hull
SPEAKER: Komei Fukuda,
Institute for Operations Research, Dept. of Mathematics, EPF-Lausanne, Switzerland.
Consider the problem of computing a minimal H-representation of the convex hull of the union of k H-polytopes in R^d. We call this problem the extended convex hull or ECH for short.
Since the usual convex hull problem is a special case in which each H-polytope is a single point (representable as the intersection of d+1 halfspaces). Our method applies the reverse search algorithm to a shelling ordering of the facets of the convex hull. Efficient wrapping is done by projecting the polytopes onto the two-dimensional space and solving a linear program. The resulting algorithm is polynomial in the sizes of input and output under the general position assumption.

(Joint work with T.M. Liebling and C. Lutolf.)


Direct questions, comments, additions to and removals from the mailing list, and suggestions for speakers to us at cgm-help@cgm.cs.mcgill.ca.