McGill University - School of Computer Science
Everybody is welcome!
Wednesday, September 6th
12:00 PM - 1:00 PM
Extended Convex Hull
Komei Fukuda, |
Institute for Operations Research, Dept. of
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