CS Seminar: Fabio Torrisi, November 18, 2003
Automatic Control Laboratory,
Swiss Federal Institute of Technology,
- Date and Time
Tuesday, November 18, 2003 at 15:45
Dipartimento di Matematica,
Università di Parma,
Via D'Azeglio 85/A,
Convexity Recognition of the Union of Polyhedra
In this talk, we consider the following basic problem in polyhedral
computation: Given two polyhedra in finite dimension, P and Q, decide
whether their union is convex, and, if so, compute it. We consider the
three natural specializations of the problem:
Both the bounded (polytopes) and the unbounded case are considered.
We show that the first two problems are polynomially solvable, and
that the third problem is strongly-polynomially solvable.
- when the polyhedra are given by halfspaces (H-polyhedra),
- when they are given by vertices and extreme rays (V-polyhedra), and
- when both H- and V-polyhedral representations are available.
Convexity Recognition of
the Union of Polyhedra (pdf, 1402 kB).
- Links to Related Publications
- Contact Person
[Page last updated on November 22, 2003, 10:38:50.]