** Next:** Is there any efficient
** Up:** Convex Polyhedron
** Previous:** Is there any efficient
** Contents**

##

Is there any efficient algorithm to compute
the intersection of two (or ) polytopes

Let , and let
be input polytopes
in , and let
be
the polytope we want to compute.

This problem of computing needs to be specified further. Namely,
what is the representation of input and that of output?

If the input polytopes are H-polytopes (given by inequalities)
then the intersection is represented by the union of
the two inequality systems. To get a minimal H-reprentation
for the intersection is just a redundancy removal given
in Section 2.21. To get a minimal V-representation
for the intersection is the vertex enumeration problem explained
in Section 2.12.

An interesting case is when both input and output polytopes
are V-polytopes (i.e. given by vertices and perhaps some
redundant points). One primitive way to solve this problem
consists of two steps: (1) generate minimal H-representations
of each of the input polytopes, (2) solve the vertex
enumeration problem for the union of
the H-representations. This naive approach might be
satisfactory for small dimensions or not-too-complicated polytopes.
Recently, a polynomial algorithm has been found for the special
case when the input polyopes are in general position [FLL00].
This algorithm is not yet practical because the general
position assumption does not seem to be easily simulated
for the general case. It should be remarked that the dual
version of this problem is to compute a minimal H-representation
of the convex hull of H-polytopes. Actually the paper [FLL00]
treats this dual problem.

** Next:** Is there any efficient
** Up:** Convex Polyhedron
** Previous:** Is there any efficient
** Contents**
Komei Fukuda
2004-08-26